Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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:

  1. Find the recursive sum of the digits of the given number
  2. 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<bits/stdc++.h>
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>>t;     //   t is the number of test cases
for(long long p=1;p<=t;p++)
{
    cin>>n;

    r=recursiveSum(n);

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

    else cout<<"Case "<<p<<": No\n";

}

}
share|improve this question

closed as off-topic by Marc-Andre, MrSmith42, BenVlodgi, syb0rg, Glenn Rogers Jun 4 at 7:02

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. Such questions may be suitable for Stack Overflow or Programmers. After the question has been edited to contain working code, we will consider reopening it." – Marc-Andre, MrSmith42, BenVlodgi, syb0rg, Glenn Rogers
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
It gives the correct answer for small values Have you tried to debug it with bigger values ? –  Marc-Andre Jun 3 at 17:38
    
Give an example of a big number which leads to a wrong result. –  MrSmith42 Jun 3 at 17:58
    
i got the bug... examples are : 7, 700, 7000, 700... and many more... as @rolfl said, recursive sum of a perfect square is always 1,4,7,9..its the necessary condition, but its not sufficient... eg -> 7,700 etc....reverse is not true in this case... –  john Jun 3 at 22:12

4 Answers 4

up vote 11 down vote accepted

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 >= 10){
        long long sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        num = sum;
     }
     return num;
  }
share|improve this answer
    
I don't think that the blog article results in a viable algorithm. It is OK for the human, but no suitable for the computer. Summing digits may require up to 20 divisions and 20 remainders - and it is still not an answer yet! Costly. Cf a binary search over a range [0, 10^9), which gives the result in at most 30 iterations, one multiplication per iteration (no divisions whatsoever). –  vnp Jun 3 at 19:45
1  
@vnp - I never intended that article as a reference for how it should be done, only why what is happening is wrong, which is a really decent start to getting it right. –  rolfl Jun 3 at 19:56
    
you are totally right... reverse isnt true...the link was quite useful... my code fails for "700" also...thts an example... half knowledge is dangerous .. i read it on some forum nd just took it the other way.. m new to this forum, but you guys are really awesome.. hats off :) –  john Jun 3 at 22:06

For the moment, I'm going to ignore the question you asked about the code, and just review the code itself.

  • Indentation needs a fair amount of work. Not really happy about some of the line breaks either. For example, I'd rather see this code:

    if(r==1 || r==4 || r==7 || r==9) cout<<"Case "<<p<<": Yes\n";
    
    else cout<<"Case "<<p<<": No\n";
    

    ...indented more like this:

    if(r==1 || r==4 || r==7 || r==9) 
        cout<<"Case "<<p<<": Yes\n";
    else 
        cout<<"Case "<<p<<": No\n";
    
  • I'd prefer to eliminate (at least some of) the code duplication. Looking at the example above, I'd prefer to see something more like:

    cout << "Case " << p;
    if (r == 1 || r==4 || r==7 || r==9)
        cout << "Yes\n";
    else
        cout << "No\n";
    
  • Looking at the recursiveSum function itself, I'd personally re-structure the code a little. I generally prefer to handle the "leaf" case immediately, then handle the recursive case:

    long long recursiveSum(long long num) { 
        if (num < 10)
            return num;
    
        while (num != 0) {
        // ...
        }
        return recursiveSum(num);
    }
    
  • I'd also prefer to use compound assignment operators, so the body of the loop is changed from:

    sum = sum + num%10;
    num = num/10;
    

    ...to:

    sum += num % 10;
    num /= 10;
    
  • Finally, I think I'd prefer to include an intermediate level of function that determines whether something is a square based on the recursive sum:

    bool is_square(long long input) {
        int val = recursiveSum(input);
    
        return val == 1 || val == 4 || val == 7 || val == 9;
    }
    
  • In C and C++, it's much more idiomatic for loops to run from 0 to N-1 than 1 to N, so in main where you have:

    for (long long p = 1; p<=t; p++)
    

    ...most C++ programmers would find it simpler to read:

    for (long long p=0; p<t; p++)
    
  • I'd also prefer to see some more explanatory names. Your comment:

    //   t is the number of test cases
    

    ... is pretty much a dead giveaway that t isn't a very good name for the variable. I'd also prefer to see variables limited to the narrowest scope possible. In this case, your input (n) has larger scope than needed. Fixing those, we get something more like this:

    int main() { 
        int num_cases; // probably no reason for a long long here.
    
        cin >> num_cases;
    
        for (int i=0; i<num_cases; i++) {
            long long input;
    
            cin >> input;
    
            cout << "Case: " << input;
            if (is_square(input))
                cout << "Yes\n";
            else
                cout << "No\n";
        }
    }
    

    In this case, you might also consider the ternary operator, giving something like this:

     cout << "Case: " input << (is_square(input) ? " Yes\n" : " No\n");
    

None of that, of course, does anything to fix the math, but as I said, I'm ignoring that part for now.

share|improve this answer
    
thanks for telling all these stuff.. helped me positively on how to structure the code... will definitely take care next time... i never thought someone will take so much time to make sure my code looks the right way.. this forum rocks.. anyways, i got the solution.. "reverse aint always true "... –  john Jun 3 at 22:10

Note that "recursive sum of the digits" winds up essentially being a way of taking the value modulo 9, with the exception that if you produce the value 9 you leave it that way rather than yielding zero. This illustrates the strengths and weaknesses of this as a (partial!) test, and suggests a solution that might be easier for machines (though more difficult for humans).

"Casting out nines" this way was a classic technique used to check calculation results, back before computers did all the work.

share|improve this answer

Your recursive sum of digits can be simplified (not that it helps the correctness of your solution).

#include <cstdlib>                                                                                                                                                                    

int recSumDigits(long long n) {                                                                                                                                                        
    while (n >= 10) {                                                                                                                                                                 
        std::lldiv_t quot_rem = std::lldiv(n, 10);                                                                                                                                    
        n = quot_rem.quot + quot_rem.rem;                                                                                                                                             
    }
    return (int)n;                                                                                                                                                                    
}
share|improve this answer
    
i was unaware about std::lldiv_t... thnks for mentioning... –  john Jun 3 at 22:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.