This content originally appeared on DEV Community and was authored by sachin26
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 missing & repeating number.
step-3 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] *= -13. check, it is already marked negative, then save it in
ansarray & 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
This content originally appeared on DEV Community and was authored by sachin26
sachin26 | Sciencx (2022-01-04T11:23:32+00:00) Striver’s SDE Sheet Journey – #11 Repeat and Missing Number. Retrieved from https://www.scien.cx/2022/01/04/strivers-sde-sheet-journey-11-repeat-and-missing-number/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.