Find the Missing Number

So in this article, we will be understanding how to find the missing number in an array. This simply means that we will have an array containing integers of size N-1 and the numbers will be from 1 to N and there will be one missing number from 1 to N which we have to find out

Problem Statement: Given an array of size N-1 containing integers between 1 to N. Find the number from the range 1 to N that is not present in the input array.

Example:

Input: N = 5

Arr = [1,2,4,5]

Output: 3 is the missing number

Solution:

Explanation:

·        N is the number till where our range ends that is from 1 to N. So using N*N+1/2 formula we get the summation of all numbers from 1 to N.

·        After this we simply calculate the sum of all the elements that are present in the array.

·        Finally we calculate the difference of these 2 sums and the answer that we get is the missing number from the range 1 to N.

Time Complexity: O(N)

Space Complexity: O(1)