PerfectSquares
TCO20 South Asia Parallel · 2020-08-15 · by erinn
Problem Statement
Perfect squares are those numbers that represent an integer multiplied by itself. Similarly, perfect cubes are third powers of integers, and so on.
We wish to generalize on this somewhat. We are interested in those integers within a given range, from minimum to maximum, inclusive, that represent an integer raised to some power n >= 2.
You are given maxN, which is the maximum power n that we wish to consider. You are also given the range of integers to consider. Return the number of integers in the given range that meet our criteria.
Constraints
- minimum will be between 1 and 10^11, inclusive.
- maximum will be between minimum and 10^11, inclusive.
- maxN will be between 2 and 30, inclusive.
1 10 3 Returns: 4
We have the range [1,10] and we are interested in all numbers in this range that are squares or cubes (or both). We have 1 (1^2 or 1^3), 4 (2^2), 8 (2^3), and 9 (3^2) in the range. Note that 1 is only counted once, even though it's both a square and a cube.
1 20 30 Returns: 5
The values that work are 1, 4, 8, 9, 16. (Note that 16 is both a square, 16 = 4^2, and a fourth power, 16 = 2^4. We still only count it once.)
100 200 2 Returns: 5
Since maxN = 2, we only want perfect squares, thus 100, 121, 144, 169, 196 all work.
144 144 2 Returns: 1
1 100000000000 30 Returns: 320989
Submissions are judged against all 20 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PerfectSquares with a public method int countRange(long long minimum, long long maximum, int maxN) · 20 test cases · 2 s / 256 MB per case