Problem Statement
For any integers p and q, both greater than one, define the [p,q]-numbers to be all integers of the form (p^i * q^j), for non-negative integers i and j. Your task is to calculate the nth-smallest [p,q]-number, where nth-smallest means that there are exactly n smaller [p,q]-numbers.
For example, the sequence of [2,3]-numbers is 1,2,3,4,6,8,9,12,..., so 12 is the nth-smallest [2,3]-number for n=7.
Create a class PQNumbers containing a method nthSmallest that takes three integers, p, q, and n, and returns the nth-smallest [p,q]-number.
Definition
- Class:
- PQNumbers
- Method:
- nthSmallest
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int nthSmallest(int p, int q, int n)
- (be sure your method is public)
Notes
- p^i means p to the i-th power, not xor.
Constraints
- p and q are both between 2 and 20, inclusive.
- n is between 0 and 20, inclusive.
- The nth-smallest [p,q]-number is no greater than 1 million.
Examples
2
2
0
Returns: 1
2
2
3
Returns: 8
2
3
7
Returns: 12
The example above.
3
5
5
Returns: 25
3
2
20
Returns: 108
10
10
5
Returns: 100000
10
9
20
Returns: 100000
20
19
10
Returns: 130321
7
5
15
Returns: 3125
10
4
15
Returns: 4000
9
6
17
Returns: 17496
2
8
10
Returns: 1024
7
13
0
Returns: 1
13
17
18
Returns: 830297
7
14
14
Returns: 19208
20
2
20
Returns: 1600
16
18
8
Returns: 5184
5
10
20
Returns: 31250
5
6
16
Returns: 3750
9
12
20
Returns: 248832
12
13
19
Returns: 342732
12
18
16
Returns: 373248
18
12
11
Returns: 31104
2
8
10
Returns: 1024
7
5
20
Returns: 15625
2
4
14
Returns: 16384
2
20
4
Returns: 16
2
8
15
Returns: 32768
2
2
2
Returns: 4
2
20
19
Returns: 1280
7
13
1
Returns: 7
2
2
3
Returns: 8
2
3
4
Returns: 6
2
2
19
Returns: 524288
2
2
9
Returns: 512
20
7
1
Returns: 7
20
13
0
Returns: 1
2
16
16
Returns: 65536