Clear C++ solution that can avoid overflow


  • 24
    U
    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            int result = 0;
            for (int i = 0; i < nums.size(); i++)
                result ^= nums[i]^(i+1);
            return result;
        }
    };

  • -1
    Z

    looks neat, but it doesn't work if the given array is not ordered.


  • 3
    J

    No, that will work. The operation of xor is commutative and associative. That is A ^ B = B^A and (A ^ B) ^ C = A ^ (B ^ C). Therefore, A^C^B^A^C = A^A^C^C^B = B. So for this code, the order of the numbers does not matter at all.


  • 0
    R
    This post is deleted!

  • 0
    R

    Thanks for your anwser. It is amazing to think about xor operation.


  • 0
    W

    Great idea, but why can we use it to get the true answer?


  • 0
    W

    OK....clear
    to remove the exist number


Log in to reply
 

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