missing-number

//https://leetcode.com/problems/missing-number/

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
  int missingNumber(vector<int>& nums) {
    if (nums.empty())
      return 0;

    int missing_num = 0;
    int max = nums.at(0);
    // find max value
    for (vector<int>::iterator it=nums.begin(); it != nums.end(); ++it){
      if (max < *it)
        max = *it;
    }

    // create arr from 0 to max+1
    int *tmp_arr = new int[max+2];
    for (int i=0; i<= max+1; i++){
      tmp_arr[i]=i;
    }

    // replace every found entry with -1
    for (int i=0; i<nums.size(); i++){
      tmp_arr[nums[i]] = -1;
    }

    // find first none -1 entry
    for (int i=0; i<= max+1; i++){
      if (tmp_arr[i] != -1){
        missing_num = i;
        break;
      }
    }

    delete[] tmp_arr;
    return missing_num;
  }
};

int main() {
  int fin;

  Solution sol;
  vector<int> myvector;
  for (int i=0;i<=10;i++) {
    if (i != 4)
      myvector.push_back(i);
  }

  cout << "vector: ";
  for (int i=0; i<myvector.size(); i++){
    cout << myvector.at(i) << " ";
  }
  cout << endl;

  fin = sol.missingNumber(myvector);
  cout << "missing: " << fin << endl;

  cin >> fin;
  return 0;
}