PowerCollector

SRM 305 · 2006-05-31 · by vorthys

SRM 305 · 2006-05-31 · by vorthys · Advanced Math, Recursion

Show categories

Class Name: PowerCollector

Return Type: String

Method Name: countPowers

Arg Types: (string)

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.

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

"1"
Returns: "1"

"10"
Returns: "4"

The powers between 1 and 10 are 1, 4, 8, and 9.

"100"
Returns: "13"

"1000"
Returns: "41"

"10000"
Returns: "125"

18)

"36"
Returns: "9"

The powers between 1 and 36 are 1, 4, 8, 9, 16, 25, 27, 32, and 36.

Submissions are judged against all 77 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PowerCollector with a public method string countPowers(string N) · 77 test cases · 2 s / 256 MB per case