Ezvor

3932. Count K-th Roots in a Range

MediumMath Preparing judge… LeetCode

You are given three integers l, r, and k.

An integer y is said to be a perfect kth power if there exists an integer x such that y = xk.

Return the number of integers y in the range [l, r] (inclusive) that are perfect kth powers.

 

Example 1:

Input: l = 1, r = 9, k = 3

Output: 2

Explanation:

The perfect cubes in the range [1, 9] are:
  • 1 = 13
  • 8 = 23
Hence, the answer is 2.

Example 2:

Input: l = 8, r = 30, k = 2

Output: 3

Explanation:

The perfect squares in the range [8, 30] are:
  • 9 = 32
  • 16 = 42
  • 25 = 52
Hence, the answer is 3.

 

Constraints:

  • 0 <= l <= r <= 109
  • 1 <= k <= 30
MathBinary Search

Hints

Hint 1
Count how many perfect kth powers are at most r, then subtract how many are less than l.
Hint 2
For k >= 2, we can bruteforce the largest x such that xk <= r .
Hint 3
Be careful of edge case: k == 1.
Hint 4
Be careful of this edge case: l == 0.