fork download 
  1. #include <functional>
  2. #include <algorithm>
  3. #include <iostream>
  4. using namespace std;
  5. template <typename T>
  6. bool IsPalindrome(const T num) {
  7.     T reverse = 0;
  8.     T n = num;
  9.     while (n > 0) {
  10.         reverse = (reverse * 10) + n % 10;
  11.         n /= 10;
  12.     }
  13.     return reverse == num;
  14. }
  15.  
  16.  
  17. template <typename T = long long int>
  18. T LongestPalindromeFromProductOfNDigitNums(int n) {
  19.     T result = 0, val = 0, max_n_digit_num = std::pow(10, n)-1,
  20.     least_n_digit_num = std::pow(10, n-1);
  21.     int n_checks = 0;
  22.     for (T i = max_n_digit_num; i >= least_n_digit_num; --i) {
  23.         if ((i*i) < result) {//found the highest palindrome
  24.             break;
  25.         }
  26.         for (T j = i; j >= least_n_digit_num; --j) {
  27.             val = i*j;
  28.             ++n_checks;
  29.             if (val < result) // any product i*j for the value of 'j' after this will be less than result
  30.                 break;
  31.             if (IsPalindrome(val)) {
  32.                 if (val > result)
  33.                     result = val;
  34.                 break;  // whenever a palindrome is found break since we only need highest one
  35.             }
  36.         }
  37.     }
  38.     std::cout << " Total num of checks = " << n_checks << std::endl;
  39.     return result;
  40. }
  41.  
  42. int main() {
  43. 	int n = 3;
  44.     std::cout << " LongestPalindromeFromProductOfNDigitNums for n = "
  45.     << n << " is " << LongestPalindromeFromProductOfNDigitNums(n) << std::endl;
  46.     n = 4;
  47.     std::cout << " LongestPalindromeFromProductOfNDigitNums for n = "
  48.     << n << " is " << LongestPalindromeFromProductOfNDigitNums(n) << std::endl;
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin 
Standard input is empty
stdout 
 Total num of checks = 6165
 LongestPalindromeFromProductOfNDigitNums for n = 3 is 906609
 Total num of checks = 2549
 LongestPalindromeFromProductOfNDigitNums for n = 4 is 99000099
https://ideone.com/WoNSJP
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!