Problem Statement
When she was in kindergarten, Elly really liked the number N. As she was still very young, she wasn't that good at math - she could only multiply by numbers between 1 and 20, inclusive. One time she started wondering what is the closest to N number she can get by multiplying only these integers.
For example, let's say Elly's number N is 404. The number is not found among the ones she can represent as a product of integers in [1, 20]. She can, however, represent the numbers 400 as 4 * 2 * 5 * 2 * 5 (the closest number smaller than 404) and 405 as 5 * 9 * 9 (the closest number larger than 404). The difference between 404 and 400 is 4, and the one between 404 and 405 is 1. Thus, here the answer is 405, since it is closer.
You are given Elly's favorite number: the long N. Return the closest to it integer, that can be represented as a product of integers between 1 and 20, inclusive. If there are two solutions, return the smaller one.
For example, let's say Elly's number N is 404. The number is not found among the ones she can represent as a product of integers in [1, 20]. She can, however, represent the numbers 400 as 4 * 2 * 5 * 2 * 5 (the closest number smaller than 404) and 405 as 5 * 9 * 9 (the closest number larger than 404). The difference between 404 and 400 is 4, and the one between 404 and 405 is 1. Thus, here the answer is 405, since it is closer.
You are given Elly's favorite number: the long N. Return the closest to it integer, that can be represented as a product of integers between 1 and 20, inclusive. If there are two solutions, return the smaller one.
Definition
- Class:
- EllysProduct
- Method:
- getClosest
- Parameters:
- long
- Returns:
- long
- Method signature:
- long getClosest(long N)
- (be sure your method is public)
Notes
- Please note that a number can be used more than once in the product. For example 405 = 5 * 9 * 9. In this case 9 was used more than once.
Constraints
- N will be between 1 and 1018, inclusive.
Examples
404
Returns: 405
The example from the problem statement.42
Returns: 42
In some cases we can get the exact number. Forty-two is just six by seven.213
Returns: 210
Here both 210 and 216 can be expressed as 14 * 15 and 8 * 3 * 9, respectively. No number between them can be expressed as a product of numbers between 1 and 20. Since both of them are equally distanced from the target number, we chose the smaller one.1337
Returns: 1331
Sometimes the closest product might be far from the number the girl likes.13
Returns: 13
The girl can get all numbers between 1 and 20 exactly.4572394873452384
Returns: 4572393450625000
A large number.
Back to all problems