TopCoder problem "NumberGuesser" used in SRM 168 (Division I Level One , Division II Level Two)



Problem Statement

    

Select two numbers between 1 and 9998, inclusive, which have the same exact group of non-zero digits, but are not the same number. For example, you could use 1234 and 4321, or 91 and 901. Now, subtract the smaller of the two numbers from the larger. Finally, pick one of the non-zero digits in the result, and remove the digit from the number. If the resulting number is less than 100, prepend enough zeros so that it has 3 digits. It turns out, that given the remaining 3 digits, one can always determine the digit removed. (See examples for clarification)

You will be given a String leftOver, which contains the three digits left over after the above algorithm is run. You must return the digit which was removed.

 

Definition

    
Class:NumberGuesser
Method:guess
Parameters:String
Returns:int
Method signature:int guess(String leftOver)
(be sure your method is public)
    
 

Notes

-Although it may not be obvious, there is only one answer for each input.
-You can only remove a non-zero digit when running the algorithm.
-HINT: work backwards from the input.
 

Constraints

-leftOver will consist of exactly 3 characters.
-Each character of leftOver will be a digit '0'-'9'.
-The input will be possible to acheive by performing the algorithm stated above.
 

Examples

0)
    
"087"
Returns: 3
Take the number 4321 and subtract 1234, you get 3087. Remove the 3, and the resulting digits are 087.
1)
    
"099"
Returns: 9
One possible way to achieve this is by using the numbers 1000 and 1.
2)
    
"191"
Returns: 7
4525 - 2554 = 1971

also, you could get this with:

1900 - 109 = 1791

or

7900 - 709 = 7191

3)
    
"689"
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4645&pm=1869

Writer:

schveiguy

Testers:

lbackstrom , brett1479

Problem categories:

Math, Simulation