TopCoder problem "MagicalSource" used in SRM 451 (Division I Level One)



Problem Statement

    Rick firmly believes that there are magical patterns related to some numbers. This belief is the result of his own tendency to find odd patterns everywhere. He has recently thought that some numbers have a "magical source". For example, the number 1371110974 has a magical source equal to 1234 because of the following process: 

        1234
+      12340
+     123400
+    1234000
+   12340000
+  123400000
+ 1234000000
------------
  1371110974
Formally, 1234 is a magical source of 1371110974 because there exists a number n such that the sum of a sequence of n numbers, where the i-th number (0-indexed) is 1234 multipled by 10^i, is equal to 1371110974. Note that by this definition, a positive number is a magical source of itself.



Given a positive long x, return its minimum positive magical source.
 

Definition

    
Class:MagicalSource
Method:calculate
Parameters:long
Returns:long
Method signature:long calculate(long x)
(be sure your method is public)
    
 

Constraints

-x will be between 1 and 1000000000000 (10^12), inclusive.
 

Examples

0)
    
1371110974
Returns: 1234
This is the example from the statement.
1)
    
111111
Returns: 1
2)
    
10989
Returns: 99
3)
    
120
Returns: 120
Note that a number is always a magical source of itself.
4)
    
109999999989
Returns: 99

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13905&pm=10635

Writer:

vexorian

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Math, Simple Math, Simple Search, Iteration