Greetings, Readers!
Welcome to our coding journey of competitive programming questions. Today, we’re diving into a classic problem “Missing Number in Array”. Join us as we dissect the problem, examine examples, and explore solutions step by step.

Understanding the Problem:

Imagine you have an array of size N-1, filled with distinct integers ranging from 1 to N but one number would be missing. Your task is to find the missing number from this array. This means, that given an array, we need to determine which number from the range 1 to N is not present.

Problem Example Walkthrough:

Let’s take a closer look at two examples to better understand the problem:

Example 1:
Input:
N = 7
A[] = {1, 2, 3, 4, 5, 7}

In this example, we’re given an array of size 7 with elements {1, 2, 3, 4, 5, 7}. The missing number is expected to be 6 since it’s the only integer in the range 1 to 7 that’s not present in the array.

Example 2:
Input:
N = 10
A[] = {1, 3, 10, 5, 4, 6, 7, 9, 8}

In this example, we’re given an array of size 10 with elements {1, 3, 10, 5, 4, 6, 7, 9, 8}. The missing number is expected to be 2 since it’s the only integer in the range 1 to 10 that’s not present in the array.

Solution 1: Sorting and Sequential Search

Let’s begin with our first solution. In this approach, we sort the array and then sequentially search for the missing number by comparing it with a sequentially incremented count. If at any point, the element in the array is not equal to our count, we’ve found the missing number.

Here’s how it works:

• Sort the given array in non-decreasing order.
• Initialise a count variable to 1.
• Iterate through the sorted array.
• If the current element matches the count, increment the count.
• If the current element does not match the count, return the count as the missing number.

If we consider example 2:

• Sort the array: {1, 3, 4, 5, 6, 7, 8, 9, 10}.
• Initialise count = 1.
• Sequentially compare each element with count:
• 1 matches count, so increment count to 2.
• 3 does not match count, so return count = 2.

Hence, the missing number is 2.

Time Complexity:

Sorting the array takes O(N log N) time, and the sequential search takes O(N) time. Therefore, the overall time complexity of this solution is O(N log N).

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& array, int n) {
        sort(array.begin(), array.end());
        int count = 1;
        for (int i = 0; i < n; i++) {
            if (array[i] == count) {
                count++;
            } else {
                return count;
            }
        }
    }
};

int main() {
    // Example 1
    int N1 = 7;
    vector<int> A1 = {1, 2, 3, 4, 5, 7};
    Solution sol1;
    int missing1 = sol1.missingNumber(A1, N1);
    cout << "Example 1 Output: " << missing1 << endl;

    // Example 2
    int N2 = 10;
    vector<int> A2 = {1, 3, 10, 5, 4, 6, 7, 9, 8};
    Solution sol2;
    int missing2 = sol2.missingNumber(A2, N2);
    cout << "Example 2 Output: " << missing2 << endl;

    return 0;
}

Solution 2: Mathematical Approach of the Problem

Our second solution takes a different route by leveraging mathematics. We know that the sum of the first N natural numbers can be calculated using the formula: sum = N * (N + 1) / 2. By finding the sum of all numbers from 1 to N and subtracting the sum of elements present in the array, we can obtain the missing number.

Here’s a breakdown:

• Calculate the sum of the first N natural numbers using the formula.
• Iterate through the given array and subtract each element from the sum.
• The remaining value after subtraction will be the missing number.

If we consider example 2:

• Calculate the sum of the first 10 natural numbers: sum = 10 * (10 + 1) / 2 = 55.
• Subtract the sum of array elements from the total sum:
• sum = 55 – (1 + 3 + 10 + 5 + 4 + 6 + 7 + 9 + 8) = 2.

Thus, the missing number is 2.

Time Complexity:

This solution has a time complexity of O(N) since it requires a single pass through the array to calculate the sum and then another pass to subtract each element.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& array, int n) {
        // Your code goes here
        int sum = n * (n + 1) / 2;
        for (int p : array) {
            sum -= p;
        }
        return sum;
    }
};

int main() {
    // Example 1
    int N1 = 7;
    vector<int> A1 = {1, 2, 3, 4, 5, 7};
    Solution sol1;
    int missing1 = sol1.missingNumber(A1, N1);
    cout << "Example 1 Output: " << missing1 << endl;

    // Example 2
    int N2 = 10;
    vector<int> A2 = {1, 3, 10, 5, 4, 6, 7, 9, 8};
    Solution sol2;
    int missing2 = sol2.missingNumber(A2, N2);
    cout << "Example 2 Output: " << missing2 << endl;

    return 0;
}

Conclusion:

After examining both solutions, we observe that while Solution 1 involves sorting and sequential searching, which could be inefficient for large arrays, Solution 2 offers a more direct and efficient approach by utilizing mathematics. Although Solution 2 seems to have a better time complexity, both solutions provide valid ways to solve the problem.

This blog post provides an overview of the “Missing number in array” problem, two solutions, and their respective time complexities. It aims to guide readers through understanding the problem and exploring various approaches to solve it.

In real-world scenarios of competitive programming, considering the size of the input array and time constraints would help in choosing the most suitable solution.

Happy coding!