StringOfPowers
TCO04 Finals · 2004-09-07 · by lbackstrom
Problem Statement
A friend of mine once told me that his phone number, 642-5616, is easy to remember because it is made up of only powers of 2: "64" + "256" + "16". This made me wonder how many numbers of various lengths had this property.
Given ints b and digits, write a method to compute how many integers of the given number of digits can be formed by concatenating various powers of the given base. Use only non-negative powers of the base (including b0, which equals 1).
For example, given b = 12, and digits = 4, there are 8 such numbers:
1111: "1" + "1" + "1" + "1"
1112: "1" + "1" + "12"
1121: "1" + "12" + "1"
1144: "1" + "144"
1211: "12" + "1" + "1"
1212: "12" + "12"
1441: "144" + "1"
1728: "1728"
Constraints
- b will be between 2 and 999999999, inclusive.
- digits will be between 1 and 18, inclusive.
12 4 Returns: 8
This is the example in the problem statement.
2 3 Returns: 89
5 2 Returns: 5
The five numbers are: 11, 15, 51, 25, and 55.
10 7 Returns: 64
The first digit must be a 1, and the remaining 6 digits can each be zero or one. Therefore, there are 26 = 64 possibilities.
1000 9 Returns: 13
Submissions are judged against all 34 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StringOfPowers with a public method long long count(int b, int digits) · 34 test cases · 2 s / 256 MB per case