Find Missing or Duplicate Number

[GreektoGreek] Find the Missing Number (or Duplicate Number), Solutions

   You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. one of the integers is missing in the list. Write an efficient code to find the missing integer.

For example: given array = [1,2,4, , 6, 3, 7, 8]
the result should be: 5


Solution 1: calculate sum from 1 to n and subtract each element from the array, the remain number is the result. Time complexity O(n).

[Code]
int Solution1(vector <int> &num, int N)
{
     int len = num.size();
     int sum = (N + 1) * N / 2;
     for(int i= 0; i< len; i++) {
         sum -= num[i];
     }
     return sum;
}

Solution 2: calculate xor sum from 1 to n and xor again with each element from the array, the remain number is the result. Time complexity: O(n).

[Code]
int Solution2(vector<int> &num, int N)
{
    int len = num.size();
    int sum = 0;
    for(int i=1; i<=N; i++)
       sum ^= i;
    for(int i= 0; i< len; i++)
       sum ^=num[i];
    return sum;
}

Solution 3: sort the whole array and compare element from 1 to n-1

if find there is a mismatch, just return the value i+1. Time complexity: O(nlogn).

[Code]
int Solution3( vector<int> & num, int N)
{
    sort(num.begin(), num.end());
    for( int i= 0; i< N-1; i++)
      if( (i+1) != num[i])
         return i+1;
}

Solution 4: Sort the whole array (O(n)) in this case and then find out the missing number:

[Code]
int Solution4(vector<int> & num, int N)
{
    int r= 0;
    while(r<N) {
      if (num[r] <N-1 && num[r] !=num[num[r]-1])
          swap(num[r], num[num[r-1]]);
      else
          r ++;
    } 
     
    for( int i= 0; i< N-1; i++)
      if( (i+1) != num[i])
         return i+1;
}

Variety of extended problems:

1. You are given a list of n-2 integers and these integers are in the range of 1 to n. There are no duplicates in list. 2 of the integers is missing in the list. Write an efficient code to find these missing integers.

Solution 1: (No code example)

Multiply and addition, let's assume that the two unknown numbers are A, B;

1) Calculate P = 1*2*...n and divided by each element from array, 
   get P = A * B;

2) Calculate S = 1+2+...+ n and subtracted by each element from array, 
   get S = A + B;

3) Combine S and P we get A and B,


Solution 4:  (time complexity O(n))

1) Calculate X = 1^2^...n, then calculate X xor each element from the array, and get X = A^B , this X indicates the different of A and B on the bit level;

2) use the bit operation to find out the number only contains the right most bit set of X and yield Y;
   get Y = X&(~X + 1)

3) using Y to divide the whole array into two groups and repeat 1) 
to separate A and B; 
     

[Code]
void Solution(vector<int> &nums, int N, int &a, int &b)
{
     int len = nums.size();
     int sum = 0;
     for( int i = 1; i<=N; i++)
        sum ^= i;
     for(int i = 0; i< len; i++)
        sum ^= nums[i];

     sum = sum &(~(sum -1)); 

     a = b = 0;

     for(int i=1; i<=N; i++)
        if((i & sum) == sum)
           a = a ^i;
        else
           b = b^i;

     for( int i = 0; i< len; i++)
        if( (nums[i] & sum) == sum)
            a = a ^ nums[i];
        else
            b = b ^ nums[i];

}

2. You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5
The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Solution:

   This is exactly the same as problem 1, because after xor the whole array, result does not include these repeated numbers, X^X = 0.

3. Find the repeating and the missing, you are given an array of size n. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.

Solution 1:
   This is exactly the same as the problem 1, because after xor the whole array, result does not include these repeated numbers, X^X = 0. (it does not ask which number is missing and which number appears twice). 

Solution 2: 
    Using auxiliary array, space O(n), time complexity O(n).
1) create an auxiliary array with size of array + 1 and initialize all of these elements to 0;
2) iterate all elements from array and increase the value of its corresponding aux elements;
3) iterate all elements from aux array, find the elements with 0 and 2 values; 

[Code]
int Solution(vector<int> & nums, int &dup, int &missing)
{
    vector<int> aux (nums.size()+1, 0);
    for (int i= 0; i< nums.size(); i++) {
         aux[nums[i]] ++;
    }

    for (int i= 1; i< aux.size(); i++) {
        if (aux[i] == 0) missing = i;
        if (aux[i] == 2) dup = i;
    }
}

4. Find a missing element in the sorted array, array elements are in range from 1 to n-1, using the most efficient way. 

For example: given an array[] = {1,2,3,4,5,7,8,9,10};  call the function should return 6;

Solution: time complexity O (log(n)):
Using binary search

  
int Solution(vector<int> & nums)
{
    int len = nums.size();
    int l = 0;
    int r = len -1;
    int mid;
    while(r>0 && l < len){
       mid = (r+l)>> 1;
       if( nums[mid] == mid+1 && nums[l] == l+1) {
           l = mid+1;
       }
       else r = mid;
       if ( r== l) break;
    }
    return r + 1;
}

5. Find a duplicate element in the sorted array, array elements are in range from 1 to n, using the most efficient way. 

For example: given an array[] = {1,2,3,4,4,5,6,7,8,9,10};  call the function should return 4;

Solution: time complexity O (log(n)):

Using binary search

 [Code] 
int Solution(vector<int> & nums)
{
    int len = nums.size();
    int l = 0;
    int r = len -1;
    int mid;
    while(r>0 && l < len){
       mid = (r+l)>> 1;
       if( nums[mid] == mid+1 && nums[l] == l+1) {
           l = mid+1;
       }
       else r = mid;
       if ( r== l) break;
    }
    return r;   // only this statement is different from the previous problem. :)
}

6. [GeeksforGeeks] Find the element that appears once.
Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space.

Examples:

Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}

Output: 2

Solutions:
   This is a very tricky solution, which requires we understand very well about the xor and bit operations:

    Trick 1:  if X = 0, then set X = a  by assigning X = X | a on the bit level.

   Trick 2:   if Y = a, then reset Y = 0 by assigning Y = Y ^ a  on the bit level.
             if Y = 0, then reset Y= a by  assigning Y= Y ^ a on the bit level.

   Trick 3:  if Z = a & b, then reset a = 0 by assigning a = ~Z & a  on the bit level.

int Solution(vector<int> & nums)
{
      int    ones = 0 ;
      int    twos = 0 ;
      int    threes = 0;
      int x ;

      for( i=0; i< nums.size(); i++ )
      {
           x =  nums[i];
          
           // calculate twos first because it requires the previous value of ones
           twos = twos | (ones & x) ;
          
           // set/reset ones 
           ones = ones ^ x ;
           
           // if both ones and twos are set, counts threes 
           threes = ones & twos ;

           // now if threes is set for value x, clear the ones and twos
           ones = ones & ~threes ;
           twos = two & ~ threes ;
       }
        return ones;
}