EllysPalMul
SRM 785 · 2020-05-08 · by espr1t
Problem Statement
This problem has a non-standard time limit: 3 seconds.
We call a number a palindrome if it reads the same from left to right as it does from right to left. For example, some palindromic numbers are 6, 11, 121, 666, 100001, and 123454321. Note that the number 47740 is not a palindrome (as you are not allowed to have unnecessary leading zeros).
Elly has the integer X. Now she wants to find the lowest integer 1 ⤠Y ⤠1,000,000,000, such that the product X * Y is a palindrome (if there is such a number).Let's look at several examples:
- If X = 42, then Y is 6 (42 * 6 = 252).
- If X = 121, then Y = 1 (121 * 1 = 121).
- If X = 1337, then Y = 143 (1337 * 143 = 191191).
- If X = 13, then Y = 38 (13 * 38 = 494).
- If X = 100, then no Y can make it a palindrome.
- If X = 21951, then Y = 9612315612 would make it a palindrome (21951 * 9612315612 = 210999939999012), but this Y isn't in the bounds [1, 10^9].
Constraints
- X will be between 1 and 100,000, inclusive.
42 Returns: 6
42 * 6 = 252
121 Returns: 1
121 is already a palindrome, so we can multiply it by 1.
1337 Returns: 143
1337 * 143 = 191191
13 Returns: 38
13 * 38 = 494
100 Returns: -1
No Y can make it a palindrome, so we return -1.
21951 Returns: -1
Y = 9612315612 would make it a palindrome (21951 * 9612315612 = 210999939999012), but since it isn't in the bounds [1, 10^9], we return -1.
Submissions are judged against all 229 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysPalMul with a public method int getMin(int X) · 229 test cases · 2 s / 256 MB per case