PerfectPowers
TCO09 Semifinal · 2009-02-24 · by mohamedafattah
TCO09 Semifinal · 2009-02-24 · by mohamedafattah · Search, Simple Math, Sorting
Problem Statement
Problem Statement
A number is called a perfect power if it can be written in the form m^k, where m and k are positive integers, and k > 1.
Given two positive integers A and B, find the two perfect powers between A and B, inclusive, that are closest to each other, and return the absolute difference between them. If less than two perfect powers exist in the interval, return -1 instead.
Given two positive integers A and B, find the two perfect powers between A and B, inclusive, that are closest to each other, and return the absolute difference between them. If less than two perfect powers exist in the interval, return -1 instead.
Notes
- 1 is a perfect power.
Constraints
- A will be between 1 and 10^18, inclusive.
- B will be between A+1 and 10^18, inclusive.
Examples
0)
1 4 Returns: 3
1 and 4 are the first pair of perfect powers.
1)
8 9 Returns: 1
8 and 9 are the closest pair of perfect powers.
2)
10 15 Returns: -1
No pair of perfect powers is present in the interval.
3)
10 24 Returns: -1
4)
9 16 Returns: 7
17)
1 1000000000000000000 Returns: 1
This is the largest possible range, and 8 and 9 are the closest pair of perfect powers.
Submissions are judged against all 151 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PerfectPowers with a public method long long nearestCouple(long long A, long long B) · 151 test cases · 2 s / 256 MB per case