XOR, one pass


  • 7
    T

    The idea is based on:
    (1 ^ 2 ^ 3 ^ .. ^ n) ^ (1 ^ 2 ^ 3 ^ .. ^ n) = 0
    Suppose we change 'a' to 'b', then all but 'a' and 'b' are XORed exactly 2 times. The result is then
    0 ^ a ^ b ^ b ^ b = a ^ b
    Let c = a ^ b, if we can find 'b' which appears 2 times in the original array, 'a' can be easily calculated by a = c ^ b.

        public int[] findErrorNums(int[] nums) {
            int n = nums.length;
            int[] count = new int[n];
            int[] ans = {0,0};
            for(int i = 0; i < n; i++) {
                ans[1] ^= (i+1) ^ nums[i];
                if (++count[nums[i]-1] == 2)
                    ans[0] = nums[i];
            }
            ans[1] ^= ans[0];
            return ans;
        }
    

    O(0) space:

        public int[] findErrorNums(int[] nums) {
            int[] ans = new int[2];
            for(int i = 0; i < nums.length; i++) {
                int val = Math.abs(nums[i]);
                ans[1] ^= (i+1) ^ val;
                if (nums[val-1] < 0) ans[0] = val;
                else nums[val-1] = -nums[val-1];
            }
            ans[1] ^= ans[0];
            return ans;
        }
    

  • 0
    S

    @tyuan73 great solutions


  • 0
    S

    @tyuan73 said in XOR, one pass:

    else nums[val-1] = -nums[val-1];

    I think the 'else' here is redundant.


  • 0
    A

    @tyuan73 good


  • 0
    H

    can you explain this solution? thanks!


  • 0
    R

    @tyuan73 said in XOR, one pass:

    if (nums[val-1] < 0) ans[0] = val;

    If you use this method to find the duplicate, then the missing can be easily founded by sum{1,...n}-sum_of_the_input_array+duplicate, hence there is no need to use xor to get 1-pass O(n)/O(1) solution.


  • 0
    T

    @rikimberley There are 2 advantages XOR over sum: 1. XOR is slightly faster; 2. sum(1..n) may overflow.


  • 0
    R

    @tyuan73 sum{1,...n}-sum_of_the_input_array can be implemented in the pass (sumdiff += (i+1)-abs(nums[i])


Log in to reply
 

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