PowerCollector | Topcoder Archive

Problem Statement

Your friends collect butterflies and stamps, but you collect numbers. Your collection of prime numbers is the finest in three counties, and your collection of transcendental numbers has been featured on national talkshows. Lately you've decided to start collecting powers, that is, numbers that can be written in the form M^K, where M and K are positive integers with K > 1. However, you're wondering how big a box you'll need to hold them all. Given a number N, represented as a String, determine how many powers lie between 1 and N, inclusive. Return the number of powers as a String with no leading zeros.

Definition

Class:: PowerCollector
Method:: countPowers
Parameters:: String
Returns:: String
Method signature:: String countPowers(String N)
(be sure your method is public)

Constraints

N will contain between 1 and 19 characters, inclusive.
Each character in N will be a digit ('0'-'9').
The first character in N will not be zero ('0').
N will represent a number between 1 and 1000000000000000000 (1018), inclusive.

Examples

```
"10"
```
```
Returns: "4"
```
The powers between 1 and 10 are 1, 4, 8, and 9.
```
"36"
```
```
Returns: "9"
```
The powers between 1 and 36 are 1, 4, 8, 9, 16, 25, 27, 32, and 36.

"1000000000000000000"

Returns: "1001003332"

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.