@jinxonik / UniLecs #266

missed_item.cpp

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

using std::cout;
using std::endl;
using std::vector;

int get_missed(const vector<int>& arr)
{
  if (arr.size() < 2) { return 0; }
  long long sum = 0;
  int min = INT_MAX;
  int max = INT_MIN;
  for (const int n : arr) {
    sum += n;
    if (n < min) { min = n; }
    if (n > max) { max = n; }
  }
  // sum of all elements including missed (calculated using min & max values) minus sum of present elements
  return (static_cast<long long>(min) + max) * (arr.size() + 1) / 2 - sum;
}

void test(const vector<int>& arr)
{
  cout << '{';
  if (arr.size() >= 1000) {
    cout << ' ' << arr.size() << " elements";
  } else {
    for (const int n : arr) {
      cout << ' ' << n;
    }
  }
  cout << " } : " << std::flush << get_missed(arr) << '\n';
}

int main()
{
  test({ 6, 8, 12, 14 });
  test({ 16, 14, 13 });

  // random arrays
  for (int i = 1; i <= 5; ++i) {
    std::random_device rnd;
    std::mt19937 rng(rnd());
    std::uniform_int_distribution<int> random;
    using pt = std::uniform_int_distribution<int>::param_type;
    vector<int> arr;
    int inc;
    do { inc = random(rng, pt{-5, 10}); } while(inc == 0);
    std::generate_n(std::back_inserter(arr), i<5 ? i*5 : 100'000'000, [n = random(rng, pt{-50, 50}), inc]() mutable { int ret = n; n += inc; return ret; });
    arr.erase(arr.begin() + random(rng, pt{1, static_cast<int>(arr.size()-2)}));
    shuffle(arr.begin(), arr.end(), rng);
    test(arr);
  }
}