# Find the next perfect square! [7 kyu]

[Find the next perfect square!](https://www.codewars.com/kata/56269eb78ad2e4ced1000013)
7 kyu

## Solution

/**
*** Author: R-CO
*** E-Mail: [e-mail]
*** Date: 2020-07-24
**/
#include <cctype>
#include <cstdlib>
#include <iostream>
using std::cout;
#include <map>;
using std::map;

using RefMap = map<long long int, long long int>;

RefMap ref_map({{1, 1}, {4, 2}});

struct TestCaseStruct {
  long long int input;
  long long int expected_output;
};

class FindTheNextPerfectSquare {
 public:
  long long int find_next_square(long long int sq) {
    long long int output = -1;

    auto it = ref_map.find(sq);
    if (it != ref_map.end()) {
      const auto target = it->second + 1;
      output = target * target;
      ref_map[output] = target;
    } else {
      auto last = ref_map.rbegin();
      if (last->first < sq) {
        auto number = last->second + 1;
        auto new_sq = number * number;
        while (new_sq < sq) {
          ref_map[new_sq] = number++;
          new_sq = number * number;
        }
        ref_map[new_sq] = number;
        if (new_sq == sq) {
          ++number;
          output = number * number;
          ref_map[output] = number;
        }
      }
    }

    return output;
  }
};

int main(int argc, char *argv[]) {
  TestCaseStruct test_cases[] = {{121, 144},
                                 {625, 676},
                                 {319225, 320356},
                                 {15241383936, 15241630849},
                                 {155, -1}};

  FindTheNextPerfectSquare solution;
  for (const auto test_case : test_cases) {
    if (solution.find_next_square(test_case.input) ==
        test_case.expected_output) {
      cout << "test case \"" << test_case.input << "\" is pass." << std::endl;
    } else {
      cout << "test case \"" << test_case.input << "\" is fail." << std::endl;
    }
  }

  return EXIT_SUCCESS;
}

## Result


###### tags: `CodeWars` `C++`