LeetCode 3932 - Count K-th Roots in a Range

Difficulty: 🟡 Medium
Topics: Math, Binary Search

Solution

Problem Understanding

This problem asks us to count how many integers in a given range [l, r] are perfect kth powers, meaning each integer can be expressed as x^k for some integer x.

In other words, given the lower bound l, the upper bound r, and an exponent k, we want to identify all integers y such that there exists an integer x with y = x^k and l <= y <= r. The result is simply the number of such integers.

The constraints provide useful information about input scale. Both l and r can be as large as 10^9, so enumerating every integer in the range is infeasible. The exponent k ranges from 1 to 30, which is relatively small. This implies that even for large ranges, the number of valid kth roots is not astronomically high because the kth root of 10^9 is at most around 10^3 for k=3 and even smaller for larger k.

Important edge cases include when l or r is 0 or 1, k is 1 (every integer is a perfect 1st power), and ranges where no perfect kth powers exist. The problem guarantees l <= r, so we do not need to handle inverted ranges.

Approaches

The brute-force approach would be to iterate over every integer y from l to r and check if y is a perfect kth power. To check this, we could take the kth root of y and verify if raising it back to k equals y. While correct, this is far too slow because r can be up to 10^9, leading to potentially a billion iterations.

The optimal approach leverages the observation that for each perfect kth power y = x^k, the integer x must lie in the range [l^(1/k), r^(1/k)]. By computing the smallest integer x_min such that x_min^k >= l and the largest integer x_max such that x_max^k <= r, we can directly count all integers x in this interval. This eliminates the need to iterate over every y in [l, r], reducing the problem to calculating kth roots efficiently. Binary search is suitable here because powers grow monotonically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(r - l + 1)	O(1)	Check each number in range individually, too slow for large ranges
Optimal	O(log(r) * log(k))	O(1)	Binary search to find smallest and largest x such that x^k falls within [l, r]

Algorithm Walkthrough

Define a helper function to compute the integer kth root of a number n. Use binary search to find the largest integer x such that x^k <= n. Start with low = 0 and high = n.
Compute x_min as the smallest integer such that x_min^k >= l. This can be done by computing the kth root of l using the helper, then checking if (x_min - 1)^k >= l to adjust.
Compute x_max as the largest integer such that x_max^k <= r. Use the same kth root helper function directly for r.
Return the count as max(0, x_max - x_min + 1). The max ensures we handle cases where no kth powers exist in the range.

Why it works: The algorithm works because the sequence of integers raised to the kth power is strictly increasing for x >= 0. By finding the bounds x_min and x_max directly, we guarantee that every integer in [x_min, x_max] produces a perfect kth power in [l, r]. There are no missed values or duplicates.

Python Solution

class Solution:
    def countKthRoots(self, l: int, r: int, k: int) -> int:
        def kth_root(n: int, k: int) -> int:
            low, high = 0, n
            while low < high:
                mid = (low + high + 1) // 2
                if mid ** k <= n:
                    low = mid
                else:
                    high = mid - 1
            return low

        x_min = kth_root(l, k)
        if x_min ** k < l:
            x_min += 1

        x_max = kth_root(r, k)

        return max(0, x_max - x_min + 1)

The helper function kth_root uses binary search to efficiently locate the integer kth root. We compute x_min carefully to ensure it is the smallest integer whose kth power is not below l. Then x_max is simply the largest integer whose kth power does not exceed r. The difference plus one gives the count of all valid kth powers.

Go Solution

func countKthRoots(l int, r int, k int) int {
    kthRoot := func(n int, k int) int {
        low, high := 0, n
        for low < high {
            mid := (low + high + 1) / 2
            pow := 1
            for i := 0; i < k; i++ {
                pow *= mid
                if pow > n {
                    break
                }
            }
            if pow <= n {
                low = mid
            } else {
                high = mid - 1
            }
        }
        return low
    }

    xMin := kthRoot(l, k)
    pow := 1
    for i := 0; i < k; i++ {
        pow *= xMin
    }
    if pow < l {
        xMin++
    }

    xMax := kthRoot(r, k)

    if xMax < xMin {
        return 0
    }
    return xMax - xMin + 1
}

The Go implementation mirrors Python logic. We compute powers iteratively to avoid integer overflow in multiplication, especially since Go does not have automatic big integers like Python. The logic for adjusting xMin and calculating the count remains the same.

Worked Examples

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

Compute x_min = ceil(root3(1)) = 1, x_max = floor(root3(9)) = 2. Count = 2 - 1 + 1 = 2. Perfect cubes are [1, 8].

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

Compute x_min = ceil(root2(8)) = 3, x_max = floor(root2(30)) = 5. Count = 5 - 3 + 1 = 3. Perfect squares are [9, 16, 25].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(r) * k)	Binary search on `x` over range `[0, r]`, each comparison takes O(k) for power calculation
Space	O(1)	Only a few integer variables are used, no extra data structures

The time complexity is efficient because the maximum number of iterations in the binary search is logarithmic in r, and k is bounded by 30.

Test Cases

# test cases
sol = Solution()

# Provided examples
assert sol.countKthRoots(1, 9, 3) == 2  # perfect cubes: 1, 8
assert sol.countKthRoots(8, 30, 2) == 3  # perfect squares: 9, 16, 25

# Edge cases
assert sol.countKthRoots(0, 0, 1) == 1  # 0^1 = 0
assert sol.countKthRoots(0, 1, 2) == 2  # 0^2 = 0, 1^2 = 1
assert sol.countKthRoots(10**9, 10**9, 1) == 1  # k=1, only 10^9
assert sol.countKthRoots(2, 3, 5) == 0  # no perfect fifth powers in range
assert sol.countKthRoots(1, 1000, 10) == 1  # only 1^10=1 in range

Test	Why
1,9,3	Normal case with small numbers and k=3
8,30,2	Normal case with small numbers and k=2
0,0,1	Edge case with zero
0,1,2	Edge case including zero and one
10^9,10^9,1	Large numbers, k=1
2,3,5	Range with no valid kth powers
1,1000,10	Only smallest kth power in range

Edge Cases

Case 1: l = 0, r = 0

Zero raised to any positive power is zero. We must ensure the algorithm counts this correctly. The binary search handles zero