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.
Definition
- Class:
- PerfectSquares
- Method:
- countRange
- Parameters:
- long, long, int
- Returns:
- int
- Method signature:
- int countRange(long minimum, long maximum, int maxN)
- (be sure your method is public)
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.
Examples
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.