Find digital roots of a number

Question

This is an ACM problem in order to finding the roots of an integer number. Here is the problem text: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=115

This is my code, but when I submit the code, I get wrong answer. In other side, I've check this code with numbers of integers and I've get the correct answer.

#include <iostream>
using namespace std;
int main() {
    unsigned long long cc = 0;
    cin >> cc;
    while (cc != 0) {
        unsigned long long sum = 0;
        while (cc > 0) {
            sum += cc % 10;
            cc = cc / 10;
            if (cc == 0 && sum > 9) { cc = sum; sum = 0; }
        }
        cout << sum;
        cin >> cc;
        cout << endl;
    }
}

Can you please help me?! Thank you.

score 2 · Accepted Answer · answered Mar 09 '14 at 19:46

2

The problem is that the input integer is larger than what would fit in an unsigned long long.

Therefore, you need to read the number as a string, and then calculate the digit sum from the string.

The following code will work:

#include <iostream>
#include <string>
using namespace std;


int main() 
{
  string inStr;
  while(cin >> inStr && inStr != "0")
  {
  unsigned long long cc = 0;
  for(string::const_iterator it = inStr.begin(); it!=inStr.end(); ++it)
    {
      cc += *it - '0';
    }

  unsigned long long sum = 0;
  do
    {
      while (cc) 
        {
          sum += cc % 10;
          cc = cc / 10;
        }
      cc = sum; 
      sum = 0; 
    }while(cc > 9);

     cout << cc << endl;
    }
    return 0;
}

answered Mar 09 '14 at 19:46

riklund

1,031
2
8
16

But you know, isn't there any problem? The question linked in the main post says that inputs are positive integers and we know that integers are at most 32KB. Although I have used the unsigned long long instead of integer. – Mohammad Mar 09 '14 at 19:51
Well, an integer may be arbitrarily large, the question doesn't refer to the size of the _datatype_ integer but rather any integer. – riklund Mar 09 '14 at 19:54
Also, _unsigned long long_ in C++ is [usually 8 byte](http://stackoverflow.com/questions/5836329/how-many-bytes-is-unsigned-long-long) – riklund Mar 09 '14 at 19:56
Just add all the digits modulo 9. That is, after `cc += *it - '0';` do a `cc %= 9;`. Final result in one loop, no further recursion necessary, no overflow, cc could be an 8bit byte. Or do they check the code for the actual implementation of repeated digit sums? – Lutz Lehmann Mar 10 '14 at 00:12

score 1 · Answer 2 · answered Aug 24 '15 at 21:26

1

I wonder why anyone didn't post this yet... :P the function returns the answer :)

int Digital_root(int a) {
  return a%9==0 ? 9:a%9;
}

answered Aug 24 '15 at 21:26

Guest

11
1

4pie0 · Answer 3 · 2014-03-09T19:35:41.347

0

Probably the problem is in that number might contain more than 2 digits and in this case such a modification is necessary:

int main() {
    unsigned long long cc = 0;
    cin >> cc;
        unsigned long long sum = 0;
        while (cc > 0) {
            sum += cc % 10;
            cc = cc / 10;
            if ( sum > 9) { cc = sum; sum = 0; }
                        ^
                   // cc == 0 will fail
        }
        cout << sum;
}

edited Mar 09 '14 at 19:35

answered Mar 09 '14 at 19:16

4pie0

29,204
9
82
118

You know, I've checked this with huge numbers and works fine. In another side, the problem says that output for each test case must be a single digit and output will finish when input was zero (0). – Mohammad Mar 09 '14 at 19:28
but input may be many digits, the version above works. Do you find any problem with this version? – 4pie0 Mar 09 '14 at 19:30
I've submit this code and again got the "wrong answer"! – Mohammad Mar 09 '14 at 19:32
Unfortunately I don't find the test case for this problem to check what is wrong! – Mohammad Mar 09 '14 at 19:36
It is said that "The input file will contain a list of positive integers, one per line." Don't you have to read from file? – 4pie0 Mar 09 '14 at 19:38
No there is a Judge Online to check the code with some test cases without any opening of files. – Mohammad Mar 09 '14 at 19:40

score 0 · Answer 4 · answered Mar 09 '14 at 19:40

0

It's not perfect code, but can work

int a = 0;
int b = 0;

while (true)
{
    cout << endl << "a: ";
    cin >> a;

    if (!a) break;

    do
    {
        while (a)
        {
            b += a%10;
            a /= 10;
        }
        a = b;
        b = 0;

    }
    while (a > 9);

    cout << endl<< "root: " << a;

answered Mar 09 '14 at 19:40

Dmitry

1

1

he needs help locating the problem. posting your solution is not an answer. – Karoly Horvath Mar 09 '14 at 19:46

score 0 · Answer 5 · answered Mar 10 '14 at 14:09

The task really asks for the remainder under division by 9.

Reason: Since 10 mod 9 == 1 and thus also 10^k mod 9 == 1, the sum of decimal digits has the same remainder under division by 9 as the number itself. Repeated sums of digits do not change the remainder, so the decimal digital root of some n is the same as n mod 9 or computing the digital sum of n modulo 9.

Reducing the code of riklund to this basic task gives

#include <iostream>
#include <string>
using namespace std;


int main() {
  string inStr;
  while(cin >> inStr && inStr != "0") {
    unsigned int cc = 0; // need only 5 bit for cc in this computation
    for(string::const_iterator it = inStr.begin(); it!=inStr.end(); ++it) {
      cc += *it - '0';
      cc %=9;
    }
    cout << cc << endl;
  }
  return 0;
}

score 0 · Answer 6 · answered Nov 05 '14 at 12:34

#include<iostream>
using namespace std;
int main()
{
    for (int i = 0; ; i++)
    {
        unsigned long int x,sum=0;
        cin >> x;

        if (x == 0)
            break;
        if (x <= 9)
        {
            sum = x;
            goto z;
        }

        while (x > 9)
        {
            while (x != 0)
            {
                sum = sum + (x%10);
                x = x / 10;
            }

            if (sum > 9)
            {
                x = sum;
                sum = 0;
            }
        }

z:
        cout << sum <<"\n";
    }
}

score 0 · Answer 7 · answered Jan 05 '15 at 15:36

//digital roots.cpp~KAUSHIK
#include<iostream>
using namespace std;
int sum(int n)
{
    int sum=0,r;

    for (;n>0;)
    {
        r=n%10;
        sum=sum+r;
        n=n/10;

    }
    return sum;
}
int main()
{   
    int n;
    cout<<"enter any number"<<endl;
    cin>>n;
    int a=n;
    n=sum(n);
    if((n/10)!=0)
    {   
    n=sum(n);
    cout<<"the digital root of "<<a<<" is"<<n;
    }
    else cout<<"the digital root of "<<a<<" is"<<n;

    return 0;

}

Your answer should contain an explanation of your code and a description how it solves the problem. — AbcAeffchen, Jan 05 '15 at 15:45

score 0 · Answer 8 · answered Jan 21 '15 at 10:22

it works for small integers

#include <iostream>
using namespace std;

int main()
{
    unsigned long long input;
    while (true)
    {
        cin >> input;
        if (input == 0) break;
        input = input - (9 * ((input - 1) / 9));
        cout << input << endl;
    }
    return 0;
}

score -1 · Answer 9 · answered Mar 09 '14 at 19:20

-1

it works simple copy that in main(), sorry for my english.

int a = 39;
int b = 0;

do
{
    while (a)
    {
        b += a%10;
        a /= 10;
    }
    a = b;
    b = 0;

}
while (a > 9);

answered Mar 09 '14 at 19:20

Dmitry

1

2

he needs help locating the problem. posting your solution is not an answer – Karoly Horvath Mar 09 '14 at 19:46

Find digital roots of a number

9 Answers9