find_missing.cc

// g++ -std=c++14 -O2 find_missing.cc

// Duration is 2.87698s
// 27341465
// Duration is 0.121498s
// 27341465

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

static constexpr auto kN = 32 * 1024 * 1024;

std::vector<int> GenerateData(size_t n) {
  std::vector<int> v;
  for (auto i = 1u; i <= n; i++)
    v.push_back(i);
  std::random_device random_device;
  std::mt19937_64 rand(random_device());
  v.erase(std::begin(v) + rand() % v.size());
  std::shuffle(std::begin(v), std::end(v), rand);
  return v;
}

class TimeTracker {
public:
  ~TimeTracker() {
    std::chrono::duration<double> duration =
        std::chrono::system_clock::now() - timestamp_;
    std::cout << "Duration is " << duration.count() << "s\n";
  }

private:
  decltype(std::chrono::system_clock::now()) timestamp_{
      std::chrono::system_clock::now()};
};

int Algorithm1(std::vector<int> v) {
  TimeTracker time_tracker;

  std::sort(std::begin(v), std::end(v));
  if (v.front() != 1)
    return 1;
  if (v.back() != kN)
    return kN;
  for (auto i = 0u; i < v.size() - 1; i++) {
    if (v[i + 1] - v[i] != 1)
      return v[i] + 1;
  }

  __builtin_unreachable();
}

int Algorithm2(std::vector<int> v) {
  TimeTracker time_tracker;

  std::vector<bool> map(kN + 1);
  for (auto n : v)
    map[n] = true;
  for (auto i = 1u; i < map.size(); i++) {
    if (!map[i])
      return i;
  }

  __builtin_unreachable();
}

int main() {
  auto v = GenerateData(kN);

  // for (auto i : v)
  //   std::cout << i << ' ';
  // std::cout << '\n';

  std::cout << Algorithm1(v) << '\n';
  std::cout << Algorithm2(v) << '\n';

  return 0;
}