EllysPalMul | Topcoder Archive

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].

Given the int X, return the lowest integer Y in the interval [1, 10^9] that makes the product X * Y a palindrome, or -1 if there is no such Y.

Definition

Class:: EllysPalMul
Method:: getMin
Parameters:: int
Returns:: int
Method signature:: int getMin(int X)
(be sure your method is public)

Constraints

X will be between 1 and 100,000, inclusive.

Examples

```
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.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.