Last Updated on April 24, 2023 by Abhishek Sharma
Arrays are an essential data structure in computer programming. They consist of a collection of elements, where each element can be accessed through an index. One of the common problems in programming is finding a missing number in the array. This article discusses different approaches to finding a missing number in array. So, without any further delay, lets us move on to our next section which is how to find the missing number in array.
How to Find Missing Number in Array
Given an array of integers with a length of n-1. The integers in the array are from the range 1 to n, but one of the numbers is missing. The task is to find the missing number in array.
Example :
Input
arr=[4,5,2,1]Output
3The missing number from range 1 to 5 is 3 from the given list of numbers
Approach 1: Using a Mathematical Formula to Find Missing Number in Array
We are aware that (n(n+1))/2 is the sum of all items in the range of 1 to n. Now calculate the total of the list’s items; the difference between these two figures indicates the list’s missing number.
Algorithm
- Sum the first n natural numbers by using the formula sumtotal=n*(n+1)/2.
- To keep the total of the array’s items, create the variable sum.
- The entire array should be traversed.
- Sum’s value should be updated to sum = sum + array[i]
- Print sumtotal – sum for the missing number.
Code Implementation of Finding Missing Number in Array
#include <bits/stdc++.h>
using namespace std;
// Function to get the missing number
int MissingNumber(int a[], int n)
{
int total = (n) * (n +1)/ 2;
for (int i = 0; i < n; i++)
total -= a[i];
return abs(total);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int ans = MissingNumber(arr, n);
cout << ans;
} Explanation: The list of items provided does not include element number 3. The missing number is discovered using the summation method.
Complexity analysis
- Time Complexity: O(n) Finding the sum of the items in a given array only requires one traverse.
- Space Complexity: O(1) No extra space needed.
Modification for Overflow
Approach
- The strategy is the same, except because integer overflow occurs when n is large, choose one number from the known numbers and deduct it from the provided numbers.
- Integer overflow won’t ever occur during implementation thanks to this method.
Algorithm to find missing number in array using mathematical formula
- Make a counter variable a = 2 and a variable sum1 = 1 to hold the missing number.
- The array should be traversed from start to finish index.
- Sum1 should now be updated as sum1 – arr[i] + a, and a should now be updated as a++.
- At the conclusion, print the missing number as a sum1.
Implementation
def MissingNumber(arr):
i, sum1 = 0, 1
n=len(arr)
for i in range(2, n + 2):
sum1 += i
sum1 -= arr[i - 2]
return sum1
# Driver Code
if __name__=='__main__':
arr=[ 1, 2 , 5 , 3 ]
ans=MissingNumber(arr)
print(ans)
class Solution {
static int MissingNumber(int arr[])
{
int n=arr.length;
int total = 1;
for (int i = 2; i <= (n + 1); i++) {
total += i;
total -= arr[i - 2];
}
return total;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 5, 3 };
System.out.println(MissingNumber(arr));
}
}
#include <iostream>
using namespace std;
int MissingNumber(int a[],int n)
{
int i, total = 1;
for (i = 2; i <= (n + 1); i++) {
total += i;
total -= a[i - 2];
}
return total;
}
// Driver Program
int main()
{
int arr[] = { 1, 2, 5, 3 };
int n= sizeof(arr)/sizeof(arr[0]);
cout<<MissingNumber(arr,n);
return 0;
}
Explanation: In 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) to find missing number in array
Explanation
- Now that a=0,b=0,b = 1 3 4 6 5, (XORing for the provided array) a = 1 2 3 4 5 6 (XORing for items beginning with 1 through n+1, where n is the length of the provided array)
- A-B will now provide the needed number 2. (XORed with the same values result is zero and only an uncommon number i.e, 2 is returned as the result )
Algorithm to Find Missing Number in Array using XOR Operator
- Make a variable b and an iterator a=0.
- Run a loop from 1 to n times, using a=ai for each iteration.
- Now execute the specified array’s loop from beginning to finish.
- B=barr[i] for every iteration
- Return the missing number back as a-b.
Code Implementation to Find Missing Number in Array using XOR Operator
class Main {
// Function to find missing number
static int MissingNumber(int arr[])
{
int n=arr.length;
int a = 0;
int b = 0;
/*For xor of all the elements in array */
for (int i = 1; i <n; i++)
a = a ^ arr[i];
/* For xor of all the elements from 1 to n+1 */
for (int i = 1; i < n + 1; i++)
b = b ^ i;
return (a ^ b);
}
/* program to test above function */
public static void main(String args[])
{
int a[] = { 1, 2, 4, 5, 6 };
int ans = MissingNumber(a);
System.out.println(ans);
}
}
#include <bits/stdc++.h>
using namespace std;
// Function to get the missing number
int MissingNumber(int arr[])
{
// For xor of all the elements in array
int a = 0;
int n= sizeof(arr)/sizeof(arr[0]);
// For xor of all the elements from 1 to n+1
int b = 0;
for (int i = 0; i < n; i++)
a =a ^ arr[i];
for (int i = 1; i <= n; i++)
b = b ^ i;
return (a ^ b);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 5, 6 };
int ans = MissingNumber(arr);
cout << ans;
}
Explanation: In the given range [1,6], 3 is missing from the array.
Complexity Analysis
- Time Complexity: O(n+n) = O(n)
- To obtain the value of a, the array just has to be traversed once.
- And a different traversal is necessary to determine the value of b.
- Space Complexity: O(1) No extra space is needed for storing any variables.
Approach 3: Using Hash (Frequency Counter) to Find the Missing Number in Array
Get the frequency of each element in the array using a dictionary, then go over the range from 1 to n and return the one whose frequency is 0.
Algorithm to Find Missing Number in Array using Hash
- Initialize a dictionary first.
- Now add the frequency of each integer in the array to the dictionary.
- Find the missing number that isn’t in the dictionary by starting your traversal from range 1 to n.
- A missing number is one that doesn’t appear in the dictionary.
- The key benefit over linear search is that a dictionary has an O(1) lookup time compared to a list’s O(n).
Code Implementation to Find Missing Number in Array using Hash
from collections import Counter
def MissingNumber(nums):
count = Counter(nums)
for i in range(len(nums)+1):
if(not count.get(i)):
return i
#Driver Program
if __name__=='__main__':
arr=[ 1, 2 , 4 , 5 , 6 ]
ans=MissingNumber(arr)
print(ans)
Explanation: When 3 is absent from the provided list of items, dict can be used to locate it.
Complexity Analysis
- Time Complexity: O(n+n) = O(n) Two traversals are required, One for populating the dictionary and the other one, to get the element that is missing in the dictionary.
- Space Complexity: O(n) Extra space is required for the dictionary.
Approach 4:(Used only for Python)
Subtract the array’s total elements’ sum from the array’s total elements plus n+1.
As an illustration, if arr=[1,2,4,5], then deduct the total number of items from the total number of elements in len(arr)+1.
Code Implementation
def MissingNumber(arr):
n=len(arr)
sum1=n*(n+1)//2
return sum1-sum(a)
# Driver program to test above function
if __name__=='__main__':
a = [1, 2, 4, 5, 6]
n = len(a)+1
ans = MissingNumber(a)
print(ans)
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.
Summary
There are several ways to handle this problem; one can be implemented if it is more suited to the particular issue at hand.
All methods deal with O(n) time complexity, although how well they do so largely depends on space optimization methods.
As a result, we now know a variety of effective methods for extracting the missing number from the supplied list of items.
The XOR (bit manipulation) approach is thought to be the most effective of all of them in terms of space and time complexity.
FAQs
Here are some frequently asked questions related to finding the missing number in array.
Q1: What is the concept of finding a missing number in array?
Ans: The concept of finding a missing number in array is to determine the integer that is not present in the given sequence of numbers.
Q2: Can I use binary search to find a missing number in array?
Ans: Yes, you can use binary search to find a missing number in array if the array is sorted.
Q3: How can I find a missing number in array if there are duplicates?
Ans: If there are duplicates in the array, you can still use the sum formula or XOR operation to find the missing number in array.
Q4: How can I find a missing number in array using sorting?
Ans: You can find a missing number in array using sorting by first sorting the array in ascending order and then iterating through the array to find the missing number.
Q5: Can I find a missing number in array without using extra space?
Ans: Yes, you can find a missing number in array without using extra space by modifying the methods used for a linear array.
Q6: How can I find a missing number in array if the array contains decimal numbers?
Ans: If the array contains decimal numbers, you cannot use the same methods as finding a missing number in a positive integer array. You will need to modify the methods or use a different approach.
Some similar blogs