DEV Community 👩‍💻👨‍💻

sachin26
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;
    }
}

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

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)

We are hiring! Do you want to be our Senior Platform Engineer? Are you capable of chipping in across sysadmin, ops, and site reliability work, while supporting the open source stack that runs DEV and other communities?

This role might just be for you!

Apply now