Given a positive integer num, return the sum of its digits. Bonus: Can you do it without using strings?
Example 1
Input
num = 123
Output
6
Explanation
Since 6 = 1 + 2 + 3Topic: Math
Computing the sum of the digits for a given integer is trivial and could be done in many ways.
Converting Digits to Strings
Converting to String, then iterate over each digit in the string to sum up the value. We can use the std::accumulate to reduce to a value – which is the sum of the digits.
1 2 3 4 5 6 | int solve(int num) { string s = std::to_string(num); return std::accumulate(begin(s), end(s), 0, [](auto &a, auto &b) { return a + b - 48; }); } |
int solve(int num) { string s = std::to_string(num); return std::accumulate(begin(s), end(s), 0, [](auto &a, auto &b) { return a + b - 48; }); }
Using python’s list comprehension to sum up the digits for a given integer:
1 2 3 | class Solution: def solvepyself, num): return sum(int(x) for x in str(num)) |
class Solution: def solvepyself, num): return sum(int(x) for x in str(num))
Iterative Approach
We can iterate the integer digits by digits from right to left. We can do this by mod by ten and divide it by ten.
1 2 3 4 5 6 7 8 | int solve(int num) { int r = 0; while (num) { r += num % 10; num /= 10; } return r; } |
int solve(int num) { int r = 0; while (num) { r += num % 10; num /= 10; } return r; }
In Python, we have to use double // to force a integer division.
1 2 3 4 5 6 7 | class Solution: def solve(self, num): s = 0 while num > 0: s += (num % 10) num = num // 10 return s |
class Solution: def solve(self, num): s = 0 while num > 0: s += (num % 10) num = num // 10 return s
Recursive Algorithm to COmpute the Sum of the Digits
The problem is inherent recursive. The terminal case is when number is zero and the sum of digits is zero. Thus, we can compute the sum recursively by each time extracting the right-most digit and calculate it recursively (smaller problem).
1 2 3 | int solve(int num) { return num == 0 ? 0 : (num % 10) + solve(num / 10); } |
int solve(int num) { return num == 0 ? 0 : (num % 10) + solve(num / 10); }
Python’s recursive implementation to compute the sum of the digits for a given positive integer.
1 2 3 | class Solution: def solve(self, num): return 0 if num == 0 else (num % 10) + self.solve(num // 10) |
class Solution: def solve(self, num): return 0 if num == 0 else (num % 10) + self.solve(num // 10)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Check if a Given String has Unique Characters?
Next Post: Compute the Nth Fibonacci Numbers using Iterative and Math Algorithms