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: How do you get the digits of a number without converting it to a string?

Use the remainder and integer division by 10. n % 10 is the last digit, and dividing n by 10 with the remainder thrown away drops that digit. Repeat until n reaches 0, and you visit every digit from right to left.

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

Both are O(d) and both are correct. The string version is shorter to write in many languages but builds a copy of the digits. The arithmetic version uses O(1) extra memory and shows the interviewer that 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.

+15 hidden tests on Submit

Hints

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

0 of 3 opened

Solution

A number does not hand you its digits one by one; you have to take it apart. You can turn it into text and read the characters, or use the two arithmetic moves that peel off the last digit: n % 10 gives it, and integer division by 10 removes it. Both take one step per digit, written d below, and d ≤ 10 here. The arithmetic version needs no extra memory.

Read the digits as text

Intuition

When you write a number down, you already see its digits. Turn n into its decimal text, 9045 becomes the four characters 9, 0, 4 and 5, then walk over the characters 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 text has d characters, one per digit, so the loop takes O(d) time, and the text itself 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

You can take a number apart without any text. 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, which is correct.

Each step removes one digit, so there are d steps, O(d) time, and only two integers live in memory, 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

The loop is short, and the mistakes are about types and the smallest input.

Using / where the language means real division. In JavaScript, TypeScript, Lua, PHP and R, 9045 / 10 is 904.5, and the loop then 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. Subtract '0' or parse the character first.
Looping while n >= 10. The loop then stops with the leading digit still in n and never adds it, so 9045 gives 9 instead of 18. Loop while n > 0, which also returns 0 for n = 0.
Printing large numbers as text in R. as.character(100000) gives "1e+05", not the six digits of the number. Use format(n, scientific = FALSE).

Frequently asked questions4

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.

How do you get the digits of a number without converting it to a string?

Use the remainder and integer division by 10. n % 10 is the last digit, and dividing n by 10 with the remainder thrown away drops that digit. Repeat until n reaches 0, and you visit every digit from right to left.

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 to write in many languages but builds a copy of the digits. The arithmetic version uses O(1) extra memory and shows the interviewer that you know how % 10 and / 10 take a number apart, which comes back in palindrome and digit reversal problems.

Python

def sumOfDigits(n):
    # Write code here

Test cases

Case 1

Case 2

Input

n = 9045

Expected