TopCoder problem "PermutationCounter" used in SRM 162 (Division I Level Three)



Problem Statement

    You have a group of non-zero digits, which are not necessarily unique. If you can insert '0' digits wherever you wish, there are an infinite number of integers which have exactly those non-zero digits. For example, given the group of digits {1, 2}, you can create the numbers 12, 21, 102, 120, 201, 210, 1002, 1020, etc. Given a potentially large number n in String format, return how many numbers that use the same exact non-zero digits are less than it. Leading zeros are not allowed.
 

Definition

    
Class:PermutationCounter
Method:count
Parameters:String
Returns:long
Method signature:long count(String n)
(be sure your method is public)
    
 

Constraints

-n will have between 1 and 50 characters, inclusive.
-n will consist only of digit characters ('0' - '9').
-n will not start with a '0'.
-There will be at most 2^63 - 1 integers with the same non-zero digits as n that are less than n
 

Examples

0)
    
"1020"
Returns: 7
From the problem statement above, we see that there are 7 values less than the given value.
1)
    
"50000000000000"
Returns: 13
Since there is only one non-zero digit in this number, the only way to increment the number is by inserting a zero after the 5. Therefore, the sequence is: 5, 50, 500, 5000, ..., 50000000000000.
2)
    
"1030000040000"
Returns: 1414
3)
    
"1901712530271201432987123"
Returns: 141588146596382454

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4615&pm=1752

Writer:

schveiguy

Testers:

lbackstrom , brett1479

Problem categories:

Advanced Math, Recursion, Search