No. 37 - Missing Number in an Array - solution

findMissingNumberInArray.cpp

// http://codercareer.blogspot.kr/2013/02/no-37-missing-number-in-array.html
// problem1 => time complexity : O(N), space complexity : O(2)
// problem2 => time complexity : O(logN), space complexity : O(3)
 

#include <iostream>
#include <assert.h>

using namespace std;

int unsortingArray1[10] = {0,1,3,2,5,7,8,4,9,10}; //6
int unsortingArray2[10] = {2,3,0,6,7,8,4,1,10,9}; //5
int unsortingArray3[10] = {1,9,2,5,8,0,10,4,6,7}; //3
int unsortingArray4[10] = {0,1,3,2,5,7,6,4,9,8}; //10

int sortingArray1[10] = {0,1,2,3,4,6,7,8,9,10}; //5
int sortingArray2[10] = {0,1,2,3,5,6,7,8,9,10}; //4
int sortingArray3[10] = {0,1,3,4,5,6,7,8,9,10}; //2
int sortingArray4[10] = {0,1,2,3,4,5,6,7,8,10}; //9

int findMissingNumber1(int *array, int length) {
  if (array == NULL || length <= 0) return -1;

  int sum1 = 0, sum2 = 0;

  for (int i = 0; i < length; i ++) {
    sum1 += array[i];
  }

  sum2 = length*(length + 1)/2;

  return sum2 - sum1;
}

int findMissingNumber2(int *array, int length) {
  if (array == NULL || length <= 0) return -1;

  int left = 0;
  int right = length - 1;

  while(left <= right) {
    int middle = (left + right) / 2;
    if (array[middle] != middle) {
      if (middle == 0 || array[middle - 1] == middle - 1) {
        return middle;
      }
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
    
  if (left == length)
    return length;

  return -1;
}

int main (void) {
  cout << "problem1 test start" << endl;

  assert(findMissingNumber1(unsortingArray1,
         sizeof(unsortingArray1)/sizeof(int)) == 6);
  assert(findMissingNumber1(unsortingArray2,
         sizeof(unsortingArray2)/sizeof(int)) == 5);
  assert(findMissingNumber1(unsortingArray3,
         sizeof(unsortingArray3)/sizeof(int)) == 3);
  assert(findMissingNumber1(unsortingArray4,
         sizeof(unsortingArray4)/sizeof(int)) == 10);

  cout << "problem1 test clear" << endl;

  cout << "problem2 test start" << endl;

  assert(findMissingNumber2(sortingArray1,
         sizeof(sortingArray1)/sizeof(int)) == 5);
  assert(findMissingNumber2(sortingArray2,
         sizeof(sortingArray2)/sizeof(int)) == 4);
  assert(findMissingNumber2(sortingArray3,
         sizeof(sortingArray3)/sizeof(int)) == 2);
  assert(findMissingNumber2(sortingArray4,
         sizeof(sortingArray4)/sizeof(int)) == 9);

  cout << "problem2 test clear" << endl;

  return 0;
}