Add digits of a number [Algorithm + Time Complexity]

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have explained the algorithm to add digits of a number N and presented the time and space complexity analysis. We have present an implementation in C Programming Language as well.

Table of contents:

  1. Algorithm to add digits of a number
  2. Pattern
  3. Time Complexity
  4. Space Complexity

Algorithm to add digits of a number

The algorithm to add digits of a number is as follows:

  • Initialize sum as 0.
  • Given a number N:
    • Extract the last digit as N % 10 (modulas)
    • Add the last digit to a sum variable
    • Update N by removing the last digit as N / 10 (division)
    • Repeat the above steps till N is greater than 0

The core idea is we extract the last digit at each stage and add it to a common variable that is initialized to 0 at the beginning. This results in the sum of all digits of a number.

Following is the pseudo-code:

sum = 0
Let input be N

// Make N positive if it is negative
If N < 0
    N = -1 * N

// Loop through all digits and get sum
while N > 0
    sum = sum + N%10
    N = N / 10
    
answer = sum

Pattern

If a number N has M digits, then the maximum value of the answer will be:

9 * M

So, if there are 5 digits, then the maximum sum will be 9 x 5 = 45.
The sum will increase and decrease across all 5 digit numbers.

If the number is of the form 8****, then the maximum sum will be 44 and minimum will be 8. If you start from 8000, the sum will begin at 8 and gradually, increase till 17 that is 8009. It will again hit a massive drop to 9 at 8010.

If you hardcode this pattern in your program, you can solve this problem much more efficiently at the cost of higher space requirements.

Time Complexity

In a given number N, there are log(N) bits.

If the number N is in base B (usually B=10), then the number of digits in N is log10N. As we are looping through all digits of the number N to find the sum, the time complexity will be O(logN).

The worst, average and best case are same for this problem as we iterate through fixed number of digits.

  • Best case time complexity: O(logN)
  • Average case time complexity: O(logN)
  • Worst case time complexity: O(logN)

Space Complexity

The space complexity of this approach is O(1) as no additional variable size memory is needed.

We only need three variable to capture the sum and extract each digit of the original number.

Implementation in C

Following is the implementation in C Programming Language to find the sum of all digits of a number N:

// Part of iq.opengenus.org
#include <stdio.h>
int main() {
	int N = 9453;
	int sum = 0;
	
	// Convert number to positive 
	// if negative
	if(N < 0)
	    N = -1 * N;
	    
	// Loop through all digits
	while(N > 0)
	{
	    sum = sum + N%10;
	    N = (int)N/10;
	}
	
	printf("%d", sum);
	return 0;
}

Output:

21

Step by step example:

  • Initial state
    N = 9453
    sum = 0

  • Step 1: Extract first digit
    sum = 0 + 3
    N = 945

  • Step 2: Extract second digit
    sum = 3 + 5
    N = 94

  • Step 3: Extract third digit
    sum = 8 + 4
    N = 9

  • Step 4: Extract fourth digit
    sum = 12 + 9
    N = 0

  • Answer
    sum = 21
    Answer is the value of sum that is 21.

With this article at OpenGenus, you must have the complete idea of how to find the sum of all digits of a number.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.