Missing in Array

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find missing number in array of 1..n. XOR approach: XOR all 1..n with all array elements.

Algorithm

1XOR all elements from 1 to n, then XOR all array elements. Result is the missing number.

Common Pitfalls

•Alternative: sum = n*(n+1)/2 - sum(array). XOR approach avoids overflow.

Missing in Array.java

Java

// Approach: XOR all indices 1..n with all array elements. Missing element = XOR result.
// Time: O(n) Space: O(1)
class Solution {

    // Note that the size of the array is n-1
    int missingNumber(int n, int arr[]) {
        int xorInd = 0;
        int xorVal = 0;
        for (int i = 1; i <= n; i++)
            xorInd ^= i;

        for (int val : arr)
            xorVal ^= val;

        return xorInd ^ xorVal;
    }
}

class Solution1 {
    int missingNum(int arr[]) {
        int n = arr.length;
        int xorInd = 0;
        for (int i = 0; i < n; i++)
            xorInd ^= arr[i];

        n = n + 1;
        if (n % 4 == 0)
            return xorInd ^ n;
        else if (n % 4 == 1)
            return xorInd ^ 1;
        else if (n % 4 == 2)
            return xorInd ^ (n + 1);
        else
            return xorInd;
    }
}

Was this solution helpful?