6Companies30days

Missing Number

Given an unsorted array Arr of size N of positive integers. One number ‘A’ from set {1, 2, …N} is missing and one number ‘B’ occurs twice in array. Find these two numbers.

Example

Input:
N = 2
Arr[] = {2, 2}
Output: 2 1
Explanation: Repeating number is 2 and 
smallest positive missing number is 1.

Solution

Auxiliary Array - Space - O(n) [Not Optimal]

Maintiaing an auxiliarry array to check indices

int *findTwoElement(int *arr, int n) {
    // code here
    vector <int> store(n+1,0);

    for( int i = 0 ; i < n ; i++ ){
       store[arr[i]]++;
    }

    int *ret = new int[2];

    for( int i = 1 ; i < n+1 ; i++ ){

        if( store[i] == 0 ) ret[1] = i;
        else if( store[i] > 1  ) ret[0] = i; 
    }

    return ret;
}

Using indices as a measure

• val *= -1 ( if arr[idx] > 0 )
• Else duplicate value

int *findTwoElement(int *arr, int n) {
    // code here

    int *ret = new int[2];

    for( int i = 0 ; i < n ; i++ ){

        int idx = abs(arr[i])-1;

        if( arr[idx] > 0 ) {
            arr[idx] *= -1;
        }
        else {
            ret[0] = abs(arr[i]);
        }

    }

    for( int i = 0 ; i < n ; i++ ){
        if( arr[i] > 0 ){
            ret[1] = i+1;
        }
    }


    return ret;
}