What's the difference?


  • 0
    P
    int singleNumber(vector<int>& nums) {
        int s[32] = {0}, ans = 0, i, j;
        for (i = 0; i < nums.size(); i++) {
            for (j = 0; j < 32; j++) {
                s[j] += nums[i]&1;
                nums[i] >>= 1;
            }
        }
        for (i = 0; i < 32; i++)
            if (s[i]%3)
                ans += pow(2, i);
        return ans;        
    }
    
    int singleNumber(vector<int>& nums) {
        int s[32] = {0}, ans = 0, i, j;
        for (i = 0; i < nums.size(); i++)
            for (j = 0; j < 32; j++) {
                s[j] += nums[i]&1;
                nums[i] >>= 1;
            }
        for (i = 31; i >= 0; i--)
            if (s[i]%3)
                ans += pow(2, i);
        return ans;        
    }
    

    The latter was accepted but the former not, why?


  • 1

    pow gives you a double, so the sum is a double, and sometimes it doesn't fit into ints and then apparently the behavior is undefined.

    I added some debugging:

            if (s[i]%3) {
                cout << ans << " + " << long(pow(2, i)) << " = " << (ans + pow(2, i));
                ans += pow(2, i);
                cout << " (becomes " << ans << ")" << endl;
            }
    

    The output is:

    0 + 4 = 4 (becomes 4)
    4 + 8 = 12 (becomes 12)
    ...
    1073741820 + 1073741824 = 2.14748e+09 (becomes 2147483644)
    2147483644 + 2147483648 = 4.29497e+09 (becomes -2147483648)
    

    You can see it goes wrong in the last addition, because the value is too large, and then it becomes INT_MIN just like it did for the questioner from that StackOverflow thread.

    Doing the same with the working solution outputs this:

    0 + 2147483648 = 2.14748e+09 (becomes -2147483648)
    -2147483648 + 1073741824 = -1.07374e+09 (becomes -1073741824)
    ...
    -16 + 8 = -8 (becomes -8)
    -8 + 4 = -4 (becomes -4)
    

    The first addition ends up "correct", though I'm guessing because it also defaults to INT_MIN, which just luckily happens to be what you need there. And after that, the values all fit into ints, so there's no problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.