## DEV Community is a community of 865,568 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

sachin26

Posted on

# Striver's SDE Sheet Journey - #11 Repeat and Missing Number

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