TopCoder problem "ReverseDistance" used in SRM 361 (Division I Level Two)



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.
 

Definition

    
Class:ReverseDistance
Method:find
Parameters:int
Returns:String
Method signature:String find(int difference)
(be sure your method is public)
    
 

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
6)
    
45
Returns: "50"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8009

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10773&pm=8009

Writer:

slex

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Greedy, Math, Search