Missing number in array : Simple Mathematical Solution

You may have experienced this as a developer where you have an array of numbers but one value is missing. Your code may break as a result of this missing number, generating incorrect results.

This blog article will discuss several approaches for locating and fixing an array’s missing number.

Method 1: Brute Force

A brute force approach is the simplest method for finding the missing number in an array. This approach is continuously looping through the array and determining if each integer is present or absent. Although this approach is straightforward and simple to use, but it can take a long time to process huge arrays.

Method 2: Summation

Applying summation is another method for finding the missing integer in an array. This approach includes adding up each number in the array to the sum, which is then subtracted from the total. The missing number will be the result. Given that it only needs one pass around the array, this method is more effective than the brute force approach.

We have picked below question from GeeksForGeeks :

Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.

Example 1:

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

Example 2:

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

Your Task :
You don't need to read input or print anything. Complete the function MissingNumber() that takes array and N as input  parameters and returns the value of the missing number.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 10⁶
1 ≤ A[i] ≤ 10⁶

Solution

// Solution by technoname.com
//{ Driver Code Starts
// Initial Template for Java

import java.io.*;
import java.util.*;

class Technoname {
    public static void main(String[] args) throws IOException {
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String[] str = br.readLine().trim().split(" ");
            int[] array = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                array[i] = Integer.parseInt(str[i]);
            }
            Solution sln = new Solution();
            System.out.println(sln.MissingNumber(array, n));
        }
    }
}
// } Driver Code Ends

// User function Template for Java

class Solution {
    int MissingNumber(int array[], int n) {
       int sum = n*(n+1)/2;
       int arrSum=0;
       for(int i=0;i<array.length;i++){
           arrSum=arrSum+array[i];
       }
        return sum-arrSum;
    }
}

Code Explanation :

First, the class “Solution” is defined. Next, a function called “MissingNumber” is defined inside the class “Solution”. This function takes in two parameters, an integer array called “array” and an integer “n”. Following that, a variable called “sum” is defined and is assigned the value of “n*(n+1)/2”.

This is the sum of the numbers from 1 to “n”, which is the total number of elements in the array. Then, another variable called “arrSum” is defined and is initially assigned the value of 0.

After that, a for loop is used to iterate through each element of the “array” parameter. During each iteration, the value of the current element in the array is added to the “arrSum” variable.

Finally, after all iterations, the function returns the difference of “sum” and “arrSum”. The value returned is the missing number in the array.

Missing number in array conclusion

It is worth noting that this solution has a time complexity of O(n) and a space complexity of O(1). This makes it an efficient solution to finding the missing number in an array.

In conclusion, finding missing numbers in an array can be a challenging task, but by using the solution outlined in this blog post, it becomes a simple and efficient process.

The missing number can be easily found by calculating the expected sum and actual sum of the numbers, then subtracting the two. This solution can therefore be used in a variety of situations, including data analysis, testing, and verification.

Thank you !!

Thank you for reading this article so far, if you know some other way to write above programs then you can leave a comment here or mail us at technonamecontact@gmail.com, So anyone can a get chance to publish their code on our website. As a result, one can improve knowledge and spread it to others

Please check most asked programming questions of strings with examples by clicking here, after that you might get a deep knowledge about string operations, in short, it will be helpful in clearing the interview.

For understanding the most important concept of data structures in an easy way you can check this article on our website.

If you like this article, then please share it with your friends and colleagues. If you have any questions or feedback, then please drop a note.

You can also follow us on Twitter for daily updates.