StringOfPowers | Topcoder Archive

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 b⁰, 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.
```
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.
```
11
```
```
2
```
```
Returns: 1
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.