Program to Find Missing Number in an Array.

Given an integer array arr[] of size n-1 containing distinct values in the range of [1, n], the task is to find the only number in the range that is missing from the array.

Example:

Input: arr[] = {1, 2, 3, 5, 6}
Output: 4

Explanation: 4 is missing from the range [1, 6]

Input: arr[] = {2, 3, 4}
Output: 1

Explanation: 1 is missing from the range [1, 4]

There are different approaches to solve the problem of finding the missing number in an array containing distinct values in the range of [1, n]. Let's discuss each of them in detail:

Approach 1: Brute Force Approach.

In this Brute Force approach, we take a straightforward method of checking each number from 1 to n if it exists in the given array. The first number that is not found in the array is considered the missing number.

Step-by-step Algorithm:

• Run a loop and Iterate through numbers from 1 to n.
• Check if each number exists in the given array.
• Return the first number that is not found in the array.

C++ Code Implementation:

// C++ code to find Missing number from array
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// function to find missing number
int findMissingNumber(vector<int>& arr, int n) {
    //Iterate through array 
    for (int i = 1; i <= n; ++i) {
        if (find(arr.begin(), arr.end(), i) == arr.end()) {
            return i;  //missing number
        }
    }
    return -1;
}

int main() {
    vector<int> arr = {1, 2, 4, 5};
    int n = arr.size();

    cout << "Missing Number: " << findMissingNumber(arr, n);
    
    return 0;
}

Output:

Missing Number: 3

• Time Complexity: O(n^2) This is a less efficient approach because the Nested loop is running for each element. 

• Space Complexity: O(1) because no extra space is used in this approach.

Approach 2: Using Mathematical Sum.

The Mathematical Sum approach leverages the sum formula for consecutive numbers (n * (n + 1)) / 2. By calculating the expected sum of numbers from 1 to n and subtracting the sum of the array's elements, we find the missing number.

Step-by-step Algorithm:

• Calculate the sum of all numbers from 1 to n using the formula (n * (n + 1)) / 2.
• Calculate the sum of the elements in the array.
• Subtract the sum of array elements from the sum of all numbers to find the missing number.

C++ Code Implementation.

// C++ code to find Missing number from array
#include <bits/stdc++.h>
using namespace std;

// function to find missing number
int findMissingNumber(vector<int>& arr, int n) {
    
    // sum of n natural number
    int expectedSum = (n * (n + 1)) / 2;

    int actualSum = accumulate(arr.begin(), arr.end(), 0);
    
    return expectedSum - actualSum;
}


int main() {
    vector<int> arr = {1, 2, 3, 5, 6};
    int n = arr.size();

    cout << "Missing Number: " << findMissingNumber(arr, n);
    
    return 0;
}

Output:

Missing Number: 4

• Time Complexity: O(n) as we are iterating through the array only once.

• Space Complexity: O(1) as no extra space is used in this approach.

Approach 3: Using Bit Manipulation (XOR)

In the XOR-based approach, we utilize the XOR operation to find the missing number. By XORing all numbers from 0 to n and then XORing the array's elements, the result is the missing number. 

Note: If the same number is XORed twice, it cancels out, leaving only the non-repeated or unique number. 

Illustration:

Example:
Input: [1, 2, 3, 5, 6]

Explanation:
(XOR of N natural number)^(XOR of Array Elements) = Missing Number

(1^2^3^4^5^6)^(1^2^3^5^6) = (1^1)^(2^2)^(3^3)^(5^5)^(6^6)^4
                          = 0 ^ 4
                          = 4

Step-by-step Algorithm:

• XOR all the numbers from 1 to n.
• Next, XOR all the elements of the given array.
• XOR operation of the calculated XOR of all numbers from 1 to n and the XOR of the array elements.
• Print the result as the missing number.

C++ Code Implementation.

// C++ code to find Missing number from array
#include <bits/stdc++.h>
using namespace std;

// function to find missing number using XOR
int findMissingNumberXOR(const std::vector<int>& arr, int n) {
    int xorSum = 0;
    //XOR n natural number
    for (int i = 0; i <= n; ++i) {
        xorSum ^= i;
    }
    for (int num : arr) {
        xorSum ^= num;
    }
    return xorSum;
}

int main() {
    vector<int> arr = {1, 2, 3, 5, 6};
    int n = arr.size();

    cout << "Missing Number: " << findMissingNumberXOR(arr, n);
    
    return 0;
}

Output:

Missing Number: 4

• Time Complexity: O(n) as we are iterating through the array to calculate XOR and also to calculate the XOR of n natural numbers.

• Space Complexity: O(1) as no extra space is used in this approach.