PermutationCounter
SRM 162 · 2003-09-03 · by schveiguy
SRM 162 · 2003-09-03 · by schveiguy · Advanced Math, Recursion, Search
Problem Statement
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.
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)
"10101010101010101010101010101010101010101010101010" Returns: 84859704298201
4)
"98765432109876543210" Returns: 2360008843617599
Submissions are judged against all 54 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PermutationCounter with a public method long long count(string n) · 54 test cases · 2 s / 256 MB per case