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"
Definition
- Class:
- StringOfPowers
- Method:
- count
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long count(int b, int digits)
- (be sure your method is public)
Constraints
- b will be between 2 and 999999999, inclusive.
- digits will be between 1 and 18, inclusive.
Examples
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
2
8
Returns: 209865
3
9
Returns: 110771
2
9
Returns: 991675
2
18
Returns: 1164755060683
3
18
Returns: 15558062291
4
18
Returns: 99559685
5
18
Returns: 24438520
6
18
Returns: 30657335
7
18
Returns: 24920676
8
18
Returns: 24169251
9
18
Returns: 24157817
10
18
Returns: 131072
11
18
Returns: 10252
763
18
Returns: 1406
329
18
Returns: 1556
999
6
Returns: 7
11
2
Returns: 1
5
18
Returns: 24438520
5
5
Returns: 89
5
3
Returns: 13
4
18
Returns: 99559685
111111111
18
Returns: 3
11111111
18
Returns: 5
11
18
Returns: 10252
111
3
Returns: 1
111111111
9
Returns: 1
90854
18
Returns: 113
5555
18
Returns: 307
897653
18
Returns: 53