20-Coding-Patterns-DesignGurus.org/6_find_all_missing_numbers.cpp

/* Problem:
 * https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
 */

#include <iostream>
#include <ostream>
#include <vector>

std::ostream &operator<<(std::ostream &out, const std::vector<int> &&nums) {
  out << "{";
  for (const int num : nums)
    out << num << ", ";
  out << "}";
  return out;
}

std::vector<int> solution(const std::vector<int> &input) {
  std::vector<bool> num_exist(input.size(), false);
  std::vector<int> missing_nums;
  for (const int num : input)
    num_exist[num - 1] = true;
  for (int i = 0, upto = input.size(); i < upto; i++) {
    if (!num_exist[i])
      missing_nums.push_back(i + 1);
  }
  return missing_nums;
}

int main() {
  std::cout << solution({4, 3, 2, 7, 8, 2, 3, 1}) << '\n'
            << solution({1, 1}) << '\n';
  return 0;
}