Recursive Digit Sum

Question

I was trying to solve this problem on hackerrank. But I got some problem. Specific problem is:

For example:

1. The sum of digits 9875 will be calculate as:

   sum(9875) = 9+8+7+5 = 29.

   sum(29) = 11.

   sum(11) = 2. (Using recursive function).

2. In my test case, (n ='9875', k=4) the number p is created by concatenating the string n k times so the initial p = 9875987598759875 ( the string '9875' repeat 4 times ).

But when i code this test case, it doesn't work. Here is my source code:

int SuperDigit(long n){
    long sum =0;
    if(n==0) return 0;
    else{
        return sum= sum +(n%10 + SuperDigit(n/10));
    }
    if(sum>10){
        return (sum%10 + SuperDigit(sum/10));
    }
     
}

int main(){
    string n;cin>>n;
    int T;cin>>T;
    string repeat;
    for(int i=0; i <T;i++){
        repeat += n;
    }
    cout<<repeat;
    long x=0;
    stringstream geek(repeat);
    geek>>x;
    long sum = SuperDigit(x);
    printf("\n%ld ",sum);
    for(int i=0;i<10;i++){
        if(sum>=10){
            sum = SuperDigit(sum);
        }
        else{
            break;
        }
    }
    printf("\n%ld ",sum);
}

If i try: n = '123' and k =3 (Expected output: 9)

My output will be correct, here is my output for this test case:

123 3
123123123
18       
9

But when i try n = '9875' and k = 4 (Expected output: 8)

My output will be wrong:

9875 4
9875987598759875
46 
1

As you can see in this test case, the first sum of all digits must be 116. But mine only show 46.

Can anyone explain for me? Thanks a lot!

Answer 1

You can simplify your program as shown below. Since you want to find the sum recursively, the below program shows one possible way of doing it.

Version 1: Using recursive function

#include <iostream>
int findDigit(int passed_num, int currentSum)
{
    int lastDigit;
    
    if (passed_num == 0) {    
        return currentSum;
    }
 
    // find the last didit
    lastDigit = passed_num % 10;
    
    currentSum+= lastDigit;
  
   //call findDigit() repeatedly
    currentSum = findDigit(passed_num / 10, currentSum);
  
    std::cout<<lastDigit<<" ";
    
    return currentSum;
}
  
int main()
{
    std::cout << "Enter a number: ";
    int input_num, sum;
    std::cin>>input_num;
    
    sum = findDigit(input_num, 0);
    
    std::cout<<"sum is: "<<sum<<std::endl;
    
     std::cout << "Enter another number: ";
     std::cin>>input_num;
    
    sum = findDigit(input_num, 0);
     std::cout<<"sum is: "<<sum<<std::endl;
    return 0;
}

Note there are simpler(other) ways of finding the sum without recursively. One such way is shown below:

Version 2: Using loop

#include <string>
#include <iostream>

int main()
{
    std::cout << "Enter a number: ";
   
    int individual_number = 0,  sum = 0;//these are local built in types so initialize them
  
    std::string input_num;
    
    std::cin >> input_num;
    
    for(char c : input_num)
    {
        individual_number = c -'0';
        std::cout<<individual_number<<" ";
        sum+= individual_number;
    }
    std::cout<<"total amount: "<<sum<<std::endl;
   // std::cout<<"The sum comes out to be: "<<sum<<std::endl;
    
    
    
  return 0;
}

Answer 2

In your current code you return prematurely in

if(n==0) return 0;
    else{
        return sum= sum +(n%10 + SuperDigit(n/10));
    }

Imagine that n == 89 so n%10 returns 9 and SuperDigit(n/10) returns 8 and you have 17 as an answer (when 8 is expected).

You can put it as

int SuperDigit(long n) {
  int result = 0;

  /* We compute digital root (sum of digits) */ 
  for (long number = n; number != 0; number /= 10)
    result += (int) (number % 10);
  
  /* if result is out of range [-9..9]
     we compute digital root again from the answer */   
  if (result < -9 || result > 9)
    result = SuperDigit(result);

  return result;
}