Checking if a number is a perfect square by recursive sum of its digits I was solving this question on an online judge.

The problem boils down to the following:


  Given a number \$n\$, where \$1 \le n \le 10^{18}\$, we need to check if it contains odd number of divisors.


I have used following facts in my code:


only perfect squares have an odd number of divisors
the recursive sum of digits of perfect squares is always 1,4,7 or 9


A possible solution is:


Find the recursive sum of the digits of the given number
Check if the recursive sum is 1 or 4 or 7 or 9. ( as the recursive sum of digits of perfect squares is always 1,4,7 or 9 )


Here is my code for it.  It gives the correct answer for small values, but when submitted to the online judge, it shows "Wrong Answer", which means there is some bug in the code.
Can anyone explain why this is happening ?

#include&lt;bits/stdc++.h&gt;
using namespace std;

 long long recursiveSum(long long num){
 long long sum = 0;
 while(num != 0){
 sum = sum + num%10;
 num = num/10;
 }
 if(sum/10 != 0){
    return recursiveSum(sum);
 }
 else{
     return sum;
 }

 }

int main()
{
long long t,r;
long long n;
cin&gt;&gt;t;     //   t is the number of test cases
for(long long p=1;p&lt;=t;p++)
{
    cin&gt;&gt;n;

    r=recursiveSum(n);

    if(r==1 || r==4 || r==7 || r==9) cout&lt;&lt;"Case "&lt;&lt;p&lt;&lt;": Yes\n";

    else cout&lt;&lt;"Case "&lt;&lt;p&lt;&lt;": No\n";

}

}
Your code works, as specified, but your specification is wrong.

Sometimes doing a code review involves fact-checking. In this case, your facts are wrong. What looked fishy to me, is the statement that:


  the recursive sum of digits of perfect squares is always 1,4,7 or 9


(well, I also checked that only perfect squares have an odd number of divisors - which is true).

What is the truth about the sum of digits? Well, it is true that all perfect squares have recursive digit sums that total 1, 4, 7, or 9, but the inverse is not true. This is obvious if you take the value 7, which is not a perfect square, but has the digit sum of 7.

When I looked around, I found this entertaining read: How to check if a number is a Perfect Square. It is quite clear that this is the second line of attack for checking whether a number is a perfect square. The first line is to check the last digit (which excludes 7, by the way).

Even once you have done (and passed) these two tests, all you can say is that the number is likely a perfect square. You still need to do the hard work to confirm it.

As an aside... why do you use recursion for the digit-sum. Something iterative would be great:

 long long iterativeSum(long long num){
     while(num &gt;= 10){
        long long sum = 0;
        while (num &gt; 0) {
            sum += num % 10;
            num /= 10;
        }
        num = sum;
     }
     return num;
  }