In this article, we will see how to find missing number in Array of 1 to n. This is one of basic coding interview question asked in my interviews.
2. Introduction to Problem Statement
We are given an integer array containing 1 to n but one of the number from 1 to n in the array is missing. Our goal is to provide optimum solution to find the missing number. Number can not be repeated in the array. For example:
Missing number in array
1
2
3
4
5
6
int[]arr1={7,5,6,1,4,2};
Missing number:3
int[]arr2={5,3,1,2};
Missing number:4
If we notice, we have numbers from range of 1 to 5, but 4 is missing in the array.
3. Using Sum Formula
Find the sum of n number using formula n=n*(n+1)/2.
Find the sum of elements present in given array.
Subtract (sum of n numbers – sum of elements present in the array).
Missing number in the array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
packageorg.arpit.java2blog;
publicclassMissingNumberMain{
publicstaticvoidmain(String[]args){
int[]arr1={7,5,6,1,4,2};
System.out.println("Missing number from array arr1: "+missingNumber(arr1));
int[]arr2={5,3,1,2};
System.out.println("Missing number from array arr2: "+missingNumber(arr2));
}
publicstaticintmissingNumber(int[]arr)
{
intn=arr.length+1;
intsum=n*(n+1)/2;
intrestSum=0;
for(inti=0;i<arr.length;i++){
restSum+=arr[i];
}
intmissingNumber=sum-restSum;
returnmissingNumber;
}
}
When you run above program, you will get below output:
Output
1
2
3
4
Missing number from arrayarr1:3
Missing number from arrayarr2:4
4. Using XOR
Another solution is to use XOR operator.
Here are steps:
Declare two variables a=arr[0] and b=1.
XOR all elements in the array with a and set it back to a.
XOR all elements in the array with b and set it back b.
Now XOR a and b and that should give us missing number.
Here is java program:
Find missing number using XOR
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
classMissingNumberMain{
// Function to find missing number
staticintgetMissingNumberXOR(intarr[],intn)
{
inta=arr[0];
intb=1;
// Find xor of all the elements in array
for(inti=1;i<n;i++)
a=a^arr[i];
// Find xor of all the elements from 1 to n+1
for(inti=2;i<=n+1;i++)
b=b^i;
intresult=a^b;
returnresult;
}
// Main method
publicstaticvoidmain(Stringargs[])
{
intarr[]={5,3,1,2};
intN=arr.length;
// Calling function
intmissingNumber=getMissingNumberXOR(arr,N);
System.out.println("Missing number from array: "+missingNumber);
}
}
Output
1
2
3
Missing number from array:4
5. Complexity of Algorithm
Time Complexity: O(N)
Space Complexity: O(1)
6. Conclusion
In this article, we covered two solutions to find missing number in the array. First solution is most simplest one to find missing number in the array while second solution uses xor operator and uses two loops to solve this problem.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
