Sum of Digits of a Number Using Recursion

64.6k
0

Given an integer n, return the sum of all digits present in the number using recursion.

The negative sign, if present, is not considered a digit.

Example 1

Input: n = 1234

Output: 10

Explanation:
The digits are 1, 2, 3, 4, and their sum is:

1 + 2 + 3 + 4 = 10

Example 2

Input: n = -507

Output: 12

Explanation:
The negative sign is ignored. The digit sum is:

5 + 0 + 7 = 12

Example 3

Input: n = 0

Output: 0

Explanation:
The only digit is 0, so the digit sum is 0.

Approach 1

A number can be processed one digit at a time using modulo and integer division.

For example, for 1234:

  • 1234 % 10 gives the last digit, 4.

  • 1234 / 10 removes the last digit and gives 123.

The recursive call finds the digit sum of the smaller number 123. When that call returns, the current last digit 4 is added to the returned sum.

This continues until the number becomes 0. At that point, no digits remain to be processed, so the recursion returns 0.

Algorithm

  • Convert n to its absolute value so that the negative sign does not affect digit processing.

  • Define a recursive function that receives the current number.

  • When the current number becomes 0, return 0 because no digits remain to be added.

  • Extract the last digit using n % 10.

  • Recursively calculate the digit sum of the remaining number using n / 10.

  • Add the current last digit to the value returned by the recursive call and return the result.

Dry Run

Sum of Digits Appraoch 1 Dry Run .png

Sum of Digits Appraoch 1 Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the sum of digits
// using recursive digit removal.
int sumDigitsHelper(long long n) {
// No digits remain
// to be processed.
if (n == 0) {
return 0;
}
int digit = n % 10;
// Add the current digit
// to the remaining digit sum.
return digit + sumDigitsHelper(n / 10);
}
public:
// Returns the sum of all digits
// in the given integer.
int sumDigits(int n) {
long long number = llabs((long long)n);
return sumDigitsHelper(number);
}
};
int main() {
int n = 1234;
Solution solution;
cout << solution.sumDigits(n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(D), where D is the number of digits in the number. One digit is processed in every recursive call.

Space Complexity: O(D), because one recursive call-stack frame is created for every digit.

Approach 2

The number can also be converted into a string so that every digit can be accessed directly using its index.

For example, 1234 becomes "1234". The recursive function processes one character at a time. The current character is converted from a digit character to its numeric value, while recursion calculates the sum of the remaining characters.

When the index reaches the end of the string, no digits remain, so the recursion returns 0.

Algorithm

  • Convert the absolute value of n into a string so that the negative sign is excluded.

  • Define a recursive function with the string and an index, where index points to the current digit.

  • When index reaches the length of the string, return 0 because every digit has already been processed.

  • Convert the character at the current index into its numeric digit value.

  • Recursively calculate the sum of the remaining digits starting from index + 1.

  • Add the current digit to the returned sum and return the result.

Dry Run

Sum of Digits Appraoch 2 Dry Run .png

Sum of Digits Appraoch 2 Dry Run .png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the digit sum
// starting from the given index.
int sumDigitsHelper(
const string& number,
int index
) {
// Every digit has
// already been processed.
if (index == number.size()) {
return 0;
}
int digit = number[index] - '0';
// Add the current digit
// to the remaining digit sum.
return digit + sumDigitsHelper(
number,
index + 1
);
}
public:
// Converts the number to a string
// and sums its digits recursively.
int sumDigits(int n) {
long long value = llabs((long long)n);
string number = to_string(value);
return sumDigitsHelper(
number,
0
);
}
};
int main() {
int n = 1234;
Solution solution;
cout << solution.sumDigits(n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(D), where D is the number of digits. Converting the number into a string and recursively processing its characters both take linear time.

Space Complexity: O(D), because the string stores D characters and the recursive call stack can also contain up to D calls.

Interview follow-up Questions

The absolute value of the number is used before recursion begins. The negative sign is not a digit and therefore does not contribute to the sum.

Recursion

Read Similar Blogs

TrieRecursionArraysData StructuresString

Word Search II

cpp #include using namespace std; class Solution { private: // Checks whether the current word can be completed from this board cell. bool dfs(vector >& board, int row, int col, const string& word,...

100.8k
StackBinary Search TreeData StructuresRecursion

Binary Search Tree Iterator

Input: Tree: root = [7, 3, 15, null, null, 9, 20] Calls: BSTIterator , next() , next() , hasNext() , next() , hasNext() , next() , hasNext() , next() , hasNext() Output: [null, 3, 7, true, 9, true,...

61.1k
Binary Search TreeRecursionStackData Structures

Two Sum in a BST: Find a Pair with a Given Sum

In the Two Sum IV - Input is a BST problem, you are given the root node of a binary search tree and an integer target k . Your task is to determine if there are any two distinct nodes within the tr...

87.6k
Comments0