Add digits of a number [Algorithm + Time Complexity]

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 log₁₀N. 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.