How to Find the Missing Number From an Array of Integers

Introduction

Consider a sequence of integers, from 1 to n. Given an array that contains n-1 of these numbers, without any predefined order, we want to find the missing number in the array. In this article, we will show two possible ways of solving this problem. The second one has a little improvement regarding space complexity.

Problem Example

Consider the sequence of integers from 1 to 5. We declare an array of length 4 and we put 4 of the 5 numbers in it:

int integerSet[] = {5, 2, 4, 1}

The missing number in the above is 3.

Find the Missing Number by a Temporary Array

In this section, we are going to describe a strategy that makes use of a temporary array of length n to keep track of the existent numbers. The missing one will be found by exclusion. We can describe the algorithm by the following steps:

• We declare the temporary array of length and initialize it with zeros
• We perform a cycle over the above array from 1 to n
• For each step of the cycle, we assign 1 to the position corresponding to the value returned by the original array
• We cycle again over the array. The index of the array containing zero is relative to the missing number and its number will be the value of the index plus one

The steps described above can be implemented easily:

@Test
public void findMissingNumberByTempArrayTest() throws Exception {
    int integerSet[] = { 5, 2, 4, 1 };
    int n = integerSet.length;
    int temp[] = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        temp[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        temp[integerSet[i] - 1] = 1;
    }

    int missingNumber = 0;
    for (int i = 0; i <= n; i++) {
        if (temp[i] == 0) {
            missingNumber = i + 1;
        }
    }
    assertEquals(3, missingNumber);
    System.out.println(missingNumber);
}

Performance Considerations

The time complexity of the above algorithm is O(n) and the space complexity is O(1).

Find the Missing Number by Sum

There is a better and simpler strategy to solve the problem. We can exploit the formula that gives the sum of the first n natural numbers, which is n(n+1)/2. We calculate the sum for the whole 1-5 sequence from the formula and then subtract the sum of the source array from it. The following code snippet shows the idea:

@Test
public void findMissingNumberBySumTest() throws Exception {
    int[] integerSet = { 5, 2, 4, 1 };
    int n = integerSet.length;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + integerSet[i];
    }
    assertEquals(3, ((n * (n + 1)) / 2 - sum));
    System.out.println(((n * (n + 1)) / 2 - sum));
}

Performance Considerations

The time complexity of the above algorithm is O(n) and the space complexity is O(1).

Conclusion

In this article, we have seen two possible ways of finding the missing numbers from a set of n-1 numbers taken from a 1-n sequence. The example code is available on GitHub.