How to Print a Missing Number in Array?

How to print a missing number in array?

Given an array of length, n-1 consists of elements from range 1 to n. One of the elements is missing from the given list. Find the missing number in the given array

Example :

Example Explanation:

Missing number from range 1 to 5 is 3 from the given list of numbers

Constraints:

• n == nums.length
• 1 <= n <=10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Approach 1: Using mathematical formula

Approach :

We know that the sum of elements from range 1 to n is: $\frac{(n(n+1)}{2}$ . Now find the sum of the elements from the given list, the difference between these two values gives the missing number from the given list.

• Algorithm :

1. Calculate the sum of first n natural numbers as sumtotal= $\frac{n*(n+1)}{2}$
2. Create a variable sum to store the sum of array elements.
3. Traverse the array from start to end.
4. Update the value of sum as sum = sum + array[i]
5. Print the missing number as sumtotal – sum

Implementation :

Python:

Java:

C++:

• Output :

• Explanation: Number 3 is missing from the given list of elements.Using summation formula missing number is obtained

Complexity analysis:

• Time Complexity : O(n) Only one traversal needed to find the sum of elements in given array.
• Space Complexity : O(1) No extra space needed.

Modification for overflow:

• Approach :

  • The approach remains the same but integer overflows when n is large, to avoid integer overflow, pick one number from known numbers and subtract one number from given numbers.
  • This way there won’t have Integer Overflow ever during implementation.

• Algorithm :

1. Create a variable sum1 = 1 which will store the missing number and a counter variable a = 2.
2. Traverse the array from start to end index .
3. Update the value of sum as sum1 = sum1 – arr[i] + a and update a as a++.
4. Print the missing number as a sum1 in the end .

Python :

Java:

C++:

• Output :

Explanation the given range [1,5], 4 is missing from the array.

Complexity Analysis:

• Time Complexity: O(n) Only one traversal is required
• Space Complexity : O(1) No extra space needed

Approach 2: Using Bit manipulation(XOR)

• Approach:

This property can be better explained using this image (Please create such image) Image 1:

• Example :

• Explanation: Now a=0,b=0

  • b = 1^ 3 ^ 4 ^ 6 ^ 5 (XORing for given array) a = 1^ 2 ^ 3 ^ 4 ^ 5 ^ 6 (XORing for elements starting from 1 to n+1, n is length of given array)
  • Now a^b : will give missing number 2 (XORed with same values result is zero and only uncommon number i.e , 2 is returned as the result )

• Algorithm :

1. Create a iterator a=0 and a variable b
2. Run a loop from 1 to n
3. For every iteration a=a^i
4. Now run a loop from start to end in given array
5. For every iteration b=b^arr[i]
6. Return the missing number as a^b

• Implementation:

Python :

Java:

C++:

• Output:

Explanation the given range [1,6], 3 is missing from the array.

Complexity Analysis :

• TIme Complexity : O(n+n) = O(n)
  • Only one traversal of the array is required for getting value of a
  • And another seperate traversal is required for getting value of b.
• Space Complexity : O(1) No extra space is needed for storing any variables.

Approach 3 :

Using Hash (Frequency Counter)

Approach :

Using a dictionary get the frequency of each element in the array and traverse the from 1 to n and return the element whose frequency is found to be 0.

Algorithm :

1. Firstly initialise an dictionary.
2. Now populate the dictionary with frequency of each number in array
3. Now start traversing from range 1 to n and find the missing number which is not present in the dictionary.
4. Missing number is the number which is not present in dictionary.

Dictionary has a lookup time of O(1) in contrast to list with O(n), this is the main advantage while compared to linear search.

Implementation:

Python:

The above code without using inbuilt counter method is as follows: Python:

• Output:

• Explanation: 3 is missing from the given list of elements, it can be found by using dict.

Complexity Analysis:

• Time Complexity: O(n+n) = O(n) Two traversels are required, One for populating dictionary and the other one, to get the element which is missing in dictionary.
• Space Complexity : O(n) Extra space is required for dictionary.

Approach 4:(Used only for Python)

• Approach:

  Take the sum of all elements in the array and subtract that from the sum of n+1 elements.

  For Example : If arr=[1,2,4,5] then take the sum of all elements in arr and subtract that from the sum of len(arr)+1 elements.

• Implementation:

• Output:

• Explanation : From the given range [1,6], 3 is missing from the array.

Complexity Analysis:

• Time Complexity : O(n) Only one traversal is required for finding the missing number in the array.
• Space Complexity : O(1) No extra space is needed.