CODEWITHSUNDEEP
java
MonkeyDluffy
MonkeyDluffy

Reputation: 39

How to find difference between these two codes? Both give same answer when executed but website says one code is partial correct

Question is Count Total Set Bits: https://www.interviewbit.com/problems/count-total-set-bits/

My solution is:

public class Solution {
    public int solve(int A) {
        long sum=0;
        long a=A+1;
        for(int i=0;i<32;i++){
            sum=sum+(((a/(int)Math.pow(2,i)))*(int)Math.pow(2,i-1) + (int)Math.max(0, a%(int)Math.pow(2,i+1)-(int)Math.pow(2,i)));
        }
        return (int)sum%1000000007;
    } }

However, it shows that my answer is only partially correct. I can say that my code and the solution they gave result in the same answer, at least up to 1000.

I checked their solution which is:

public class Solution {
    public int solve(int A) {
        long val1,val2,cnt;
        cnt = 0;
        for(int i = 1;i<32;i++){
            val1 = (int)((A+1)/Math.pow(2,i));
            val2 = (int)((A+1)%Math.pow(2,i));
            if(val2 > Math.pow(2,i-1))
                val2 = val2 - (int)Math.pow(2,i-1);
            else
                val2 = 0;
            cnt = cnt + (int)(val1*Math.pow(2,i-1)) + val2;
        }
       
       return (int)(cnt%1000000007);
    }
}

I find this code is using the exact same formula I am using but divided into parts and lines. So what should I correct in my code? (I am a beginner with Java.)

Upvotes: 4

Views: 142

Answers (1)

Brian McCutchon
Brian McCutchon

Reputation: 8594

The problem in your code is here:

(int)Math.pow(2,i)

This will overflow when i is 31, as 2^31 is just barely too big for an int (the largest int is 2^31 - 1). The other solution gets around this by not doing the cast until after the division.

Upvotes: 5

Related Questions