Largest Palindromic Product
National Olympiad — Regional round (2017 season)
Submission name: palindromes.cpp
Problem summary
Find the largest palindromic number that is the product of two positive integers less than N. Print its factors in increasing order. If multiple factor pairs give the maximum, choose the pair with the smallest first factor.
Input
An integer N.
Output
The two factors on the first line, followed by the maximum palindromic product on the second.
Constraints
2 ≤ N ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
100
Output
91 99 9009
Solution analysis
- There are fewer than one million candidate factor pairs under the limit, so enumerate a from 1 to N − 1 and b from a to N − 1. Restricting a ≤ b avoids counting the same unordered pair twice.
- Test a product for palindromicity by reversing its decimal string and comparing it with the original. Replace the best pair for a larger palindrome, or for an equal palindrome with a smaller a.
- For N = 100 the maximum is 9009, obtained from 91 × 99. For N = 2, the only pair is 1 × 1, so the answer is factors 1 and 1 with product 1.
Why it works
The loops visit every pair of positive factors below N exactly once in increasing factor order. The string test accepts exactly products whose decimal digits read the same in both directions. The update rule retains the maximum accepted product and then the smallest first factor, so its final pair satisfies both optimization rules.
Watch out. Factors must be strictly less than N. Include equal factors and product 1. Preserve the required tie-break on the smaller factor.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int bestProduct = 0;
int bestA = 1;
int bestB = 1;
for (int a = 1; a < n; ++a) {
for (int b = a; b < n; ++b) {
int product = a * b;
string digits = to_string(product);
string reversed = digits;
reverse(reversed.begin(), reversed.end());
// Compare palindrome value first, then the smaller factor.
if (digits == reversed && (product > bestProduct || (product == bestProduct && a < bestA))) {
bestProduct = product;
bestA = a;
bestB = b;
}
}
}
cout << bestA << ' ' << bestB << '\n';
cout << bestProduct << '\n';
return 0;
}