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