Johnnn

Let's go

Find missing number among 1 to n, in the given array of size n-1, algorithm and time complexity with example in C,C++,Python and java

by · Published · Updated


It is not uncommon to encounter scenarios where we need to find a missing number from a given array containing elements from 1 to N, where N is the expected size of the array. In this blog post, we will discuss a widely used algorithm to solve this problem efficiently. Additionally, we will provide code examples in four popular programming languages: C, C++, Python, and Java

Algorithm:
The algorithm to find a missing number among 1 to N in a given array relies on the concept of summation. The first step is to calculate the expected sum of all numbers from 1 to N using the formula (N * (N + 1)) / 2. Next, we iterate over each element in the array and subtract its value from the expected sum. At the end of this process, the remaining value will be the missing number.

Time Complexity:
The time complexity of this algorithm is O(n), where n is the size of the array. The algorithm involves a single pass through the array, making it highly efficient.

Code Examples:

  1. C:
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int expectedSum = (n * (n + 1)) / 2;
    int actualSum = 0;

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

    return expectedSum - actualSum;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]) + 1;

    int missingNumber = findMissingNumber(arr, n);

    printf("The missing number is: %dn", missingNumber);

    return 0;
}
  1. C++:
#include <iostream>
#include <vector>

using namespace std;

int findMissingNumber(vector<int>& arr, int n) {
    int expectedSum = (n * (n + 1)) / 2;
    int actualSum = 0;

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

    return expectedSum - actualSum;
}

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

    int missingNumber = findMissingNumber(arr, n);

    cout << "The missing number is: " << missingNumber << endl;

    return 0;
}
  1. Python:
def find_missing_number(arr, n):
    expected_sum = (n * (n + 1)) // 2
    actual_sum = sum(arr)

    return expected_sum - actual_sum

arr = [1, 2, 4, 5, 6]
n = len(arr) + 1

missing_number = find_missing_number(arr, n)

print("The missing number is:", missing_number)
  1. Java:
class Main {
    static int findMissingNumber(int[] arr, int n) {
        int expectedSum = (n * (n + 1)) / 2;
        int actualSum = 0;

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

        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.length + 1;

        int missingNumber = findMissingNumber(arr, n);

        System.out.println("The missing number is: " + missingNumber);
    }
}

Conclusion:
In this blog post, we delved into an efficient algorithm to find a missing number among 1 to N in a given array. By calculating the expected sum and subtracting the actual sum of the elements in the array, we can easily identify the missing number. We provided code examples in C, C++, Python, and Java, along with explanations for each step of the algorithm. Next time you encounter a similar problem, you can confidently employ this algorithm as a solution. Happy coding!

You may also like...