Find the Missing Number in an array

Given an array containing n distinct numbers from the range 1 to n+1, where exactly one number is missing, find the missing number. The array contains all numbers except for one, and the task is to identify that missing number.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [1, 2, 4, 5, 6]
Output: 3
Explanation: The numbers from 1 to 6 are expected, and 3 is missing.

Example 2:
Input:
arr = [1, 3, 4, 5]
Output: 2
Explanation: The numbers from 1 to 5 are expected, and 2 is missing.

Example 3:
Input:
arr = [2, 3, 4, 5, 6, 7, 8]
Output: 1
Explanation: The numbers from 1 to 8 are expected, and 1 is missing.

Approach to find the missing number in an array

  1. Calculate the Expected Sum of Numbers:

    • For a sequence of numbers from 1 to n+1, the expected sum can be calculated using the formula: Sum=2(n+1)×(n+2)​
    • Here, n is the length of the array.

  2. Calculate the Actual Sum of Array Elements:

    • Traverse the array and compute the sum of its elements.

  3. Find the Missing Number:

    • The missing number is the difference between the expected sum and the actual sum: Missing Number = Expected Sum−Actual Sum

C++ Program to find the missing number in an array

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the missing number in the array
int findMissingNumber(vector<int>& arr) {
    int n = arr.size();
    int expectedSum = (n + 1) * (n + 2) / 2;
    int actualSum = 0;

    // Calculate the actual sum of elements in the array
    for (int num : arr) {
        actualSum += num;
    }

    // Return the difference between expected and actual sums
    return expectedSum - actualSum;
}

int main() {
    vector<int> arr = {1, 2, 4, 5, 6};
    int missingNumber = findMissingNumber(arr);
    cout << "The missing number is: " << missingNumber << endl;
    return 0;
}

Java Program to find the missing number in an array

java
public class MissingNumber {

    // Function to find the missing number in the array
    public static int findMissingNumber(int[] arr) {
        int n = arr.length;
        int expectedSum = (n + 1) * (n + 2) / 2;
        int actualSum = 0;

        // Calculate the actual sum of elements in the array
        for (int num : arr) {
            actualSum += num;
        }

        // Return the difference between expected and actual sums
        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int missingNumber = findMissingNumber(arr);
        System.out.println("The missing number is: " + missingNumber);
    }
}

Python Program to find the missing number in an array

python
# Function to find the missing number in the array
def find_missing_number(arr):
    n = len(arr)
    expected_sum = (n + 1) * (n + 2) // 2
    actual_sum = sum(arr)
    
    # Return the difference between expected and actual sums
    return expected_sum - actual_sum

# Example usage
if __name__ == "__main__":
    arr = [1, 2, 4, 5, 6]
    missing_number = find_missing_number(arr)
    print("The missing number is:", missing_number)

Time Complexity:

  • O(n): The algorithm iterates through the array once to calculate the sum, resulting in linear time complexity.

Space Complexity:

  • O(1): The algorithm uses a constant amount of extra space.

DSA

6963

881

Related Articles