#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;
template <typename T>
bool IsPalindrome(const T num) {
    T reverse = 0;
    T n = num;
    while (n > 0) {
        reverse = (reverse * 10) + n % 10;
        n /= 10;
    }
    return reverse == num;
}


template <typename T = long long int>
T LongestPalindromeFromProductOfNDigitNums(int n) {
    T result = 0, val = 0, max_n_digit_num = std::pow(10, n)-1,
    least_n_digit_num = std::pow(10, n-1);
    int n_checks = 0;
    for (T i = max_n_digit_num; i >= least_n_digit_num; --i) {
        if ((i*i) < result) {//found the highest palindrome
            break;
        }
        for (T j = i; j >= least_n_digit_num; --j) {
            val = i*j;
            ++n_checks;
            if (val < result) // any product i*j for the value of 'j' after this will be less than result
                break;
            if (IsPalindrome(val)) {
                if (val > result)
                    result = val;
                break;  // whenever a palindrome is found break since we only need highest one
            }
        }
    }
    std::cout << " Total num of checks = " << n_checks << std::endl;
    return result;
}

int main() {
	int n = 3;
    std::cout << " LongestPalindromeFromProductOfNDigitNums for n = "
    << n << " is " << LongestPalindromeFromProductOfNDigitNums(n) << std::endl;
    n = 4;
    std::cout << " LongestPalindromeFromProductOfNDigitNums for n = "
    << n << " is " << LongestPalindromeFromProductOfNDigitNums(n) << std::endl;
	return 0;
}