Connection Status:
Competition Arena > PowerOfInteger

PowerOfInteger

TCCC07 Sponsor 2 · 2007-07-30 · by andrewzta

TCCC07 Sponsor 2 · 2007-07-30 · by andrewzta · Math, Search, Simple Math
Class Name: PowerOfInteger
Return Type: int
Method Name: greatestPower
Arg Types: (string, string)
Problem Statement

Problem Statement

A number y is said to be the k-th power of a number x if y = x^k, i.e., y is the product of k copies of x.

You are given two Strings left and right. Return the greatest k such that there is an integer y (left <= y <= right) such that y is the k-th power of some integer x.

Constraints

  • left will be an integer between 2 and 10^12, inclusive, without extra leading zeroes.
  • right will be an integer between left and 10^12, inclusive, without extra leading zeroes.
Examples
0)
"5"
"20"
Returns: 4

The greatest power between 5 and 20 is 16=2^4.

1)
"10"
"12"
Returns: 1

No nontrivial power of integer between 10 and 12, so return 1.

2)
"2"
"100"
Returns: 6
3)
"1000000000000"
"1000000000000"
Returns: 12
4)
"549755813888"
"549755813888"
Returns: 39
165)
"732082482176"
"732082482176"
Returns: 5

One that gives doubles a bit of difficulty

166)
"274794888224"
"274794888224"
Returns: 5

Another hard case for doubles

167)
"706395741416"
"706395741416"
Returns: 3

Another double trap, the other direction

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

Coding Area

Language: C++17 · define a public class PowerOfInteger with a public method int greatestPower(string left, string right) · 213 test cases · 2 s / 256 MB per case

Submitting as anonymous