TopCoder problem "StringOfPowers" used in TCO04 Finals (Division I Level Three)



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

0)
    
12
4
Returns: 8
This is the example in the problem statement.
1)
    
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.
2)
    
11
2
Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5886&pm=3006

Writer:

legakis

Testers:

PabloGilberto , lbackstrom , Yarin , vorthys

Problem categories:

Dynamic Programming, Simple Math