Problem Statement :-
You are given a read-only array of N integers with values also in the range [1,N] both inclusive. Each integer appears exactly once except A which appears twice and B which is missing. The task is to find the repeating and missing numbers A and B where A repeats twice and B is missing.
Input : array[] = {3,1,2,5,3}
Result : [3,4]
Explanation: A = 3 , B = 4
Since 3 is appearing twice and 4 is missing
Solution 1
using sorting,we can easily solve this problem.
step-1 sort the array.
step-2 traverse the array,while traversing check if A[i] == A[i+1]
is true, that should be our repeating number.
step-3 again traverse the array,and check if A[i] != i+1
is true, that should be our missing number.
step-4 end.
Java
public class Solution {
public int[] repeatedNumber(final int[] A) {
int[] ans = new int[2];
Arrays.sort(A);
// look for repeating number
for(int i=0;i<A.length-1;i++){
if(A[i] == A[i+1]) ans[0] = A[i];
}
// look for missing number
for(int i=0;i<A.length-1;i++){
if(A[i] != i+1){
ans[1] = i+1;
break;
}
}
return ans;
}
}
Time Complexity : O(n) + O(n)
Space Complexity : O(1)
Solution 2
since we know the array numbers range is 1 to N, so we can use the array indices for storing the array elements.
step-1 initialize an array ans
for storing the missing & repeating numbers.
step-2 run a loop from i=0
to n
, then
1. get the absolute ith value from the array.
index = A[i]
2. marked as visited, multiply by -1.
A[index] *= -1
3. check, it is already marked negative, then save it in
ans
array & again mark it.
ans[0] = abs(A[i])
A[index] *= -1
step-3 again traverse the array and check which number is positive, that is our missing number
step-4 end.
Java
public class Solution {
public int[] repeatedNumber(final int[] A) {
int[] ans = new int[2];
for(int i=0; i<A.length;i++){
int index = Math.abs(A[i]) - 1;
// mark as visited
A[index] *= -1;
if(A[index] > 0){
ans[0] = Math.abs(A[i]);
A[index] *= -1;
}
}
for(int i=0; i<A.length;i++){
if(A[i] > 0){
ans[1] = i+1;
}
}
return ans;
}
}
Time Complexity : O(n) + O(n)
Space Complexity : O(1)
thank you for reading this article, if you find any mistakes, let me know in the comment section
Top comments (0)