Sum of Digits

Q: What is the time complexity of summing the digits of a number?

One step per digit, so O(d) , where d is the number of digits. A number n has about log10(n) + 1 digits, so the same bound is often written O(log n) . For a 32-bit integer that is at most 10 steps.

Q: Is the string version or the arithmetic version better?

Both are O(d) and both are correct. The string version is shorter in many languages but builds a copy of the digits. The arithmetic version uses O(1) extra memory and shows you know how % 10 and / 10 take a number apart, which comes back in palindrome and digit reversal problems.

BeginnerMath and simulation

+10

You get a non-negative integer n. Return the sum of its decimal digits. For example, the digits of 482 are 4, 8 and 2, so the answer is 14.

Function

sumOfDigits(n: integer) → integer

ninteger: the non-negative integer whose digits you add
Returnsinteger: the sum of the decimal digits of n

Constraints

0 ≤ n ≤ 2³¹-1

Examples

Input: n = 9045
Output: 18
Explanation: The digits of 9045 are 9, 0, 4 and 5, and 9 + 0 + 4 + 5 = 18. The zero adds nothing but still counts as a digit.

Input: n = 7
Output: 7
Explanation: A one-digit number is its own digit sum, so 7 gives 7.

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Take the number apart one digit at a time. You can read its decimal text, or peel off the last digit with n % 10 and drop it with integer division by 10. Both take one step per digit, written d, and d ≤ 10 here. The arithmetic version needs no extra memory.

Read the digits as text

Intuition

Turn n into its decimal text, so 9045 becomes the characters 9, 0, 4 and 5, and add the value of each one.

A character is not a number yet. The character '4' is stored as the code 52, so you parse it or subtract the code of '0': '4' - '0' = 4. Digit characters have consecutive codes, which is why that subtraction works for all ten.

The loop takes O(d) time, and the text takes O(d) extra space.

Algorithm

Convert n to its decimal text.
Set total = 0.
For each character, add its digit value to total.
Return total.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Peel off the last digit with % 10

Intuition

The remainder of a division by 10 is the last digit: 9045 % 10 = 5. Integer division by 10 throws that digit away: 9045 / 10 = 904 when the fraction is dropped. Repeat the pair and the digits come out from right to left.

For 9045: add 5 and keep 904, add 4 and keep 90, add 0 and keep 9, add 9 and keep 0. The loop stops at 0 with a total of 18. For n = 0 the loop never runs and the answer is 0.

There are d steps and only two integers in memory: O(d) time, O(1) space. Every intermediate value is smaller than n, so nothing can overflow.

Algorithm

Set total = 0.
While n > 0, add n % 10 to total.
Divide n by 10, dropping the fraction.
When n reaches 0, return total.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Pitfalls and edge cases

Using / where the language means real division. In JavaScript, TypeScript, Lua, PHP and R, 9045 / 10 is 904.5, and the loop adds fractions. Round down with Math.floor or math.floor; in Python use //, in Dart ~/, in PHP intdiv, in R %/%.
Adding characters instead of digits. The character '7' has code 55, not 7.
Looping while n >= 10. The leading digit stays in n unadded, so 9045 gives 9 instead of 18.
Turning large numbers into text in R. as.character(100000) gives "1e+05"; use format(n, scientific = FALSE).

Frequently asked questions3

What is the time complexity of summing the digits of a number?

One step per digit, so O(d), where d is the number of digits. A number n has about log10(n) + 1 digits, so the same bound is often written O(log n). For a 32-bit integer that is at most 10 steps.

What is the digital root of a number?

It is what you get by summing the digits again and again until one digit is left: 9045 gives 18, then 9. For a positive n it equals 1 + (n-1) % 9, because every number leaves the same remainder when divided by 9 as its digit sum does.

Is the string version or the arithmetic version better?

Both are O(d) and both are correct. The string version is shorter in many languages but builds a copy of the digits. The arithmetic version uses O(1) extra memory and shows you know how % 10 and / 10 take a number apart, which comes back in palindrome and digit reversal problems.

def sumOfDigits(n):
    # Write code here

Test #1

Test #2

Argument

n = 9045

Expected Output