Find one missing number from 1 to N

Find one missing number from 1 to N

Given an array of size N-1, containing integer numbers from 1 to N, but there is one number missing. Return the missing number.

Analysis

Assuming the array given is A[], it’s easy to get N since we have the size of the array: N = A.length + 1.

Approach 1(Brute force):

The solution of $O(N)$ time and $O(N)$ space is intuitive. We can use a boolean array flag[] of size N, setting all of them to false initially. Then we can scan through A[], if we get value A[i], we can just set flag[A[i] – 1] to true. After we finish scanning, we can go through flag[] to see which value is false. If flag[j] is false, then the missing number is j + 1.

Approach 2(Sorting):

If we can modify the given array, we can use sorting to solve this problem. However, we won’t use the regular $O(NlogN)$ sorting method. Since the range of numbers in this array is only from 1 to N, we can use swapping to sort the array. When we scan the array at position i, if A[i] is not equal to i + 1, we can swap it with A[A[i] – 1], if A[i] is not N. After swapping, we can go through this array to see which number is missing. The array is sorted, so it’s easy to find the missing number. The complexity of this method is O(N), you can check the code below.

Approach 3(Sum):

If we cannot modify the given array, there are still some ways to reach $O(N)$. Since we already know N, it’s easy to calculate the sum of $1+2+…+N$, which is just $\frac{N(N+1)}{2}$. And we can calculate the sum $S$ of the array. Then the missing number will be $n=\frac{N(N+1)}{2}-S$. However, it’s possible that N is quite big that the sum of the array can overflow. Using long could solve this problem but it’s not a good idea. We have a better approach to use XOR.

Approach 4(XOR):

We know that a number XOR with itself will be 0. And any number XOR 0 will still be that number. So we can go through the array and calculate the XOR value by x = A[0] XOR A[1] XOR A[2] XOR …. XOR A[N – 1]. Then we can XOR x with numbers from 1 to N to get the missing number: n = x XOR 1 XOR 2 XOR 3 …. XOR N. The other numbers except the missing number will eventually XOR with itself to become 0. The missing number will be XOR with zeros, which is still itself. So the result is just what we want.

Code

// Brute force
public int findMissingNumberBruteForce(int[] A) {
    int N = A.length + 1;
    boolean[] flag = new boolean[N];
    // Of course you can combine these two for-loops together.
    for (int i = 0; i < A.length; i++) {
        flag[A[i] - 1] = true;
    }
    for (int i = 0; i < N; i++) {
        if (!flag[i])
            return i + 1;
    }
    return N;
}

// Sum
public int findMissingNumberWithSum(int[] A) {
    int N = A.length + 1;
    int sum = 0;
    // sum can overflow here.
    for (int i = 1; i <= N; i++) {
        sum += i;
    }
    for (int i = 0; i < A.length; i++) {
        sum -= A[i];
    }
    return sum;
}

// Sorting
public int findMissingNumberWithSorting(int[] A) {
    int N = A.length + 1;
    int i = 0;
    while (i < A.length) {
        // Correct position
        if (A[i] == i + 1)
            i++;
        else {
            // If A[i] is N, we are not able to swap it with other elements.
            if (A[i] == N)
                i++;
            else {
                // Swap the element.
                int tmp = A[i];
                A[i] = A[A[i] - 1];
                A[tmp - 1] = tmp;
            }
        }
    }
    // Try to find mismatch. If there is no mismatch, the missing number is N.
    for (int j = 0; j < A.length; j++) {
       if (A[j] != j + 1)
           return j + 1;
    }
    return N;
}

// XOR
public int findMissingNumber(int[] A) {
    int N = A.length + 1;
    int n = 0;
    // Of course you can combine these two for-loops together.
    for (int i = 0; i < A.length; i++) {
        n = n ^ A[i];
    }
    for (int i = 1; i <= N; i++) {
        n = n ^ i;
    }
    return n;
}

// Brute force

public int findMissingNumberBruteForce(int[] A) {

int N = A.length + 1;

boolean[] flag = new boolean[N];

// Of course you can combine these two for-loops together.

for (int i = 0; i < A.length; i++) {

flag[A[i] - 1] = true;

}

for (int i = 0; i < N; i++) {

if (!flag[i])

return i + 1;

}

return N;

}

// Sum

public int findMissingNumberWithSum(int[] A) {

int N = A.length + 1;

int sum = 0;

// sum can overflow here.

for (int i = 1; i <= N; i++) {

sum += i;

}

for (int i = 0; i < A.length; i++) {

sum -= A[i];

}

return sum;

}

// Sorting

public int findMissingNumberWithSorting(int[] A) {

int N = A.length + 1;

int i = 0;

while (i < A.length) {

// Correct position

if (A[i] == i + 1)

i++;

else {

// If A[i] is N, we are not able to swap it with other elements.

if (A[i] == N)

i++;

else {

// Swap the element.

int tmp = A[i];

A[i] = A[A[i] - 1];

A[tmp - 1] = tmp;

}

// Try to find mismatch. If there is no mismatch, the missing number is N.

for (int j = 0; j < A.length; j++) {

if (A[j] != j + 1)

return j + 1;

}

return N;

}

// XOR

public int findMissingNumber(int[] A) {

int N = A.length + 1;

int n = 0;

// Of course you can combine these two for-loops together.

for (int i = 0; i < A.length; i++) {

n = n ^ A[i];

}

for (int i = 1; i <= N; i++) {

n = n ^ i;

}

return n;

}

More things…

This problem can be changed to “Find two missing numbers from 1 to N”. I am going to cover it in the next post.