ReverseDistance
SRM 361 · 2007-08-01 · by slex
SRM 361 · 2007-08-01 · by slex · Greedy, Math, Search
Problem Statement
Problem Statement
To obtain the reverse of a number, write it backwards from right to left. For example, the reverse of 1234 is 4321, and the reverse of 100 is 1 (leading zeroes are always ignored). Return the smallest non-negative number x, such that the difference x - reverse(x) is equal to difference. If no such number exists, return "NONE" (quotes for clarity) instead.
Constraints
- difference will be between 1 and 1000000, inclusive.
Examples
0)
18 Returns: "20"
20 - 2 = 18. 18 can be also achieved in other ways like 42 - 24, but 20 is the smallest possible number.
1)
15 Returns: "NONE"
It's impossible to find a number with a difference of 15.
2)
4275 Returns: "5080"
5080 - 805 = 4275
3)
900 Returns: "101001"
101001 - 100101 = 900
4)
1989 Returns: "100990"
100990 - 99001 = 1989
5)
857232 Returns: "860300"
860300 - 3068 = 857232
Submissions are judged against all 104 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ReverseDistance with a public method string find(int difference) · 104 test cases · 2 s / 256 MB per case