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.
144
144
2
Returns: 1
1
100000000000
30
Returns: 320989
65050043084
72245082396
14
Returns: 13880
94567651677
98489102586
25
Returns: 6378
50144917620
90101410329
26
Returns: 77046
53531489030
84449700361
6
Returns: 59861
7833634728
98924042788
26
Returns: 228699
5433572543
26305028540
12
Returns: 89714
57913220659
90767553797
14
Returns: 61259
97900316199
99598663461
28
Returns: 2729
179108258
50435988296
5
Returns: 214378
78139325221
99248660033
18
Returns: 35864
133742
66642133713
30
Returns: 261894
1
10000000000
25
Returns: 102229
10
100000000000
30
Returns: 320985
2
100000000000
30
Returns: 320988
64
64
30
Returns: 1