3932. Count K-th Roots in a Range

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

An integer y is said to be a perfect k^th power if there exists an integer x such that y = x^k.

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

In other words, you need to count how many values in [l, r] can be written as some integer raised to the power k. For example, if k = 2, you are counting perfect squares (like 1, 4, 9, 16, ...); if k = 3, you are counting perfect cubes (like 1, 8, 27, ...). When k = 1, every integer is a perfect 1st power, so the answer is simply the total count of integers in the range.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Binary Search?

This problem maps to Binary Search through a short path in the full flowchart.

Binary search works because the feasibility condition is monotonic.

Open in Flowchart

Intuition

The key observation is that we are looking for numbers of the form x^k that fall inside the range [l, r]. Instead of checking every number in the range to see whether it is a perfect kth power (which could be very slow when the range is large), we can directly generate the perfect kth powers one by one.

Notice that as x increases, the value x^k grows very quickly. So the number of integers x for which x^k stays within [l, r] is actually quite small. This means we can simply start from x = 0 and keep computing x^k, incrementing x step by step. As long as x^k does not exceed r, we check whether it lies within [l, r], and count it if it does. Once x^k becomes larger than r, there is no point in continuing, since all later values will only be bigger — so we can stop immediately.

There is also a special case worth handling first: when k = 1, every integer y satisfies y = y^1, meaning every value in the range qualifies as a perfect 1st power. In this situation the answer is simply the count of integers in the range, which is r - l + 1. Separating out this case lets us avoid unnecessary enumeration and keeps the main loop focused on the cases where k >= 2.

Pattern Learn more about Math and Binary Search patterns.

Solution Approach

Solution 1: Enumeration

First, we check if k equals 1. If it does, the count of perfect 1st powers in the range is just the count of integers in the range, which is r - l + 1. We return this value directly.

Otherwise, we initialize an answer counter ans = 0 and enumerate integers x starting from 0. For each x, we compute y = x^k.

If y exceeds r, we stop the enumeration, because every subsequent value of x^k will only be larger and can never fall back into the range.
If y lies within the range [l, r], we increment ans by 1.

After the loop ends, we return ans as the final result.

Here, count() (from Python's itertools) is used to generate an unbounded sequence of integers 0, 1, 2, ..., and we rely on the break condition to terminate once x^k grows beyond r. Since x^k increases rapidly, the loop runs only about r^(1/k) times.

The time complexity is O(r^(1/k)), where the enumeration count grows slowly as k increases. The space complexity is O(1).

Example Walkthrough

Let's trace through a small example with l = 4, r = 30, and k = 2. We want to count how many perfect squares fall within the range [4, 30].

Step 1: Check the special case k = 1.

Since k = 2 (not 1), we skip the shortcut and proceed to the enumeration loop. We initialize ans = 0.

Step 2: Enumerate x starting from 0, computing y = x^k.

We walk through each value of x one at a time:

`x`	`y = x^2`	Compare with `r = 30`	In range `[4, 30]`?	Action
0	0	`0 <= 30`, continue	`0 < 4`, no	skip
1	1	`1 <= 30`, continue	`1 < 4`, no	skip
2	4	`4 <= 30`, continue	`4 <= 4 <= 30`, yes	`ans = 1`
3	9	`9 <= 30`, continue	`4 <= 9 <= 30`, yes	`ans = 2`
4	16	`16 <= 30`, continue	`4 <= 16 <= 30`, yes	`ans = 3`
5	25	`25 <= 30`, continue	`4 <= 25 <= 30`, yes	`ans = 4`
6	36	`36 > 30`, break	—	stop loop

Step 3: Return the result.

When x = 6, we get y = 36, which exceeds r = 30. Since every later value of x^2 will only grow larger, we stop immediately. The final answer is ans = 4.

The four perfect squares in [4, 30] are 4 (= 2²), 9 (= 3²), 16 (= 4²), and 25 (= 5²) — matching our count.

Notice that even though the range spans 27 integers, the loop only ran 7 times (x from 0 to 6). This reflects the O(r^(1/k)) time complexity: instead of scanning all numbers in [l, r], we directly generate the perfect powers, which grow rapidly and quickly leave the range.

Solution Implementation

1from itertools import count
2
3
4class Solution:
5    def countKthRoots(self, left: int, right: int, k: int) -> int:
6        # When k == 1, every integer x satisfies x^1 = x,
7        # so every number in the range [left, right] qualifies.
8        if k == 1:
9            return right - left + 1
10
11        answer = 0
12        # Iterate over non-negative integers as candidate bases.
13        for base in count():
14            power = base ** k
15            # Once the k-th power exceeds the right bound,
16            # all subsequent powers will be even larger, so stop.
17            if power > right:
18                break
19            # Count this power if it falls within the range [left, right].
20            if left <= power <= right:
21                answer += 1
22        return answer
23

1class Solution {
2    /**
3     * Counts how many perfect k-th powers fall within the inclusive range [left, right].
4     * A number n is counted if there exists an integer base such that base^k == n
5     * and left <= n <= right.
6     *
7     * @param left  the lower bound of the range (inclusive)
8     * @param right the upper bound of the range (inclusive)
9     * @param k     the exponent used to compute the powers
10     * @return the count of integers in [left, right] that are perfect k-th powers
11     */
12    public int countKthRoots(int left, int right, int k) {
13        // When k == 1, every integer is its own first power,
14        // so every value in [left, right] qualifies.
15        if (k == 1) {
16            return right - left + 1;
17        }
18
19        int count = 0;
20
21        // Iterate over candidate bases starting from 0, computing base^k each time.
22        for (int base = 0; ; base++) {
23            long power = 1;
24
25            // Multiply 'base' by itself k times to obtain base^k.
26            // Use a long to avoid overflow and short-circuit early
27            // once the running product exceeds 'right'.
28            for (int i = 0; i < k; i++) {
29                power *= base;
30                if (power > right) {
31                    break;
32                }
33            }
34
35            // Once base^k exceeds 'right', all larger bases will too,
36            // so we can stop the search.
37            if (power > right) {
38                break;
39            }
40
41            // If the computed power lies within the range, count it.
42            if (left <= power && power <= right) {
43                count++;
44            }
45        }
46
47        return count;
48    }
49}
50

1class Solution {
2public:
3    int countKthRoots(int l, int r, int k) {
4        // When k == 1, every integer x in [l, r] satisfies x^1 = x,
5        // so the count is simply the size of the range.
6        if (k == 1) {
7            return r - l + 1;
8        }
9
10        int ans = 0;
11
12        // Enumerate possible bases x starting from 0.
13        // For each x, compute x^k and check whether it lies within [l, r].
14        for (int base = 0;; ++base) {
15            long long power = 1;
16
17            // Compute power = base^k, but stop early if it exceeds r
18            // to avoid unnecessary multiplications and overflow.
19            for (int i = 0; i < k; ++i) {
20                power *= base;
21                if (power > r) {
22                    break;
23                }
24            }
25
26            // Once the k-th power surpasses r, no larger base can fit
27            // inside the range, so we can terminate the search.
28            if (power > r) {
29                break;
30            }
31
32            // If base^k falls within the inclusive range [l, r], count it.
33            if (l <= power && power <= r) {
34                ++ans;
35            }
36        }
37
38        return ans;
39    }
40};
41

1/**
2 * Counts how many perfect k-th powers fall within the inclusive range [l, r].
3 *
4 * A number v is counted if there exists a non-negative integer x such that
5 * x ^ k === v and l <= v <= r.
6 *
7 * @param l - The lower bound of the range (inclusive).
8 * @param r - The upper bound of the range (inclusive).
9 * @param k - The exponent used to generate the k-th powers.
10 * @returns The count of integers in [l, r] that are perfect k-th powers.
11 */
12function countKthRoots(l: number, r: number, k: number): number {
13    // When k === 1, every integer is trivially its own first power,
14    // so all integers in [l, r] qualify.
15    if (k === 1) {
16        return r - l + 1;
17    }
18
19    let count = 0;
20
21    // Iterate over candidate bases x = 0, 1, 2, ... and compute x ^ k.
22    for (let base = 0; ; base++) {
23        // Compute power = base ^ k incrementally, stopping early once it
24        // exceeds the upper bound r to avoid unnecessary multiplication
25        // and potential overflow.
26        let power = 1;
27        for (let i = 0; i < k; i++) {
28            power *= base;
29            if (power > r) {
30                break;
31            }
32        }
33
34        // If even the smallest viable power exceeds r, no larger base can
35        // produce a value within range, so terminate the search.
36        if (power > r) {
37            break;
38        }
39
40        // Count the power only if it lies within the inclusive range [l, r].
41        if (l <= power && power <= r) {
42            count++;
43        }
44    }
45
46    return count;
47}
48

Time and Space Complexity

Time Complexity: O(r^(1/k) · k)

When k == 1, the function returns immediately in O(1). For k >= 2, the loop iterates over x = 0, 1, 2, ... and stops as soon as x**k > r. The loop terminates when x reaches approximately r^(1/k), so the number of iterations is O(r^(1/k)). Each iteration computes x**k, which requires O(k) multiplications (or O(log k) with fast exponentiation, but treating the power operation as O(k) here). Therefore, the total time complexity is O(r^(1/k) · k).
Space Complexity: O(1)

Only a constant number of variables (ans, x, y) are used, regardless of the input size. No additional data structures that scale with the input are allocated, so the space complexity is O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Starting the Enumeration from `base = 0` and Mishandling `0^k`

A subtle but common mistake is mishandling the base case where base = 0. In the given code, the loop starts from 0, so the first computed value is 0 ** k = 0.

If the range is something like [1, 100], then 0 is correctly skipped because the check left <= power <= right fails (since 0 < 1).
However, if left = 0, then 0 is a valid kth power (0 = 0^k) and should be counted. This works correctly here, but problems arise if you "optimize" by starting the loop at base = 1 to avoid the trivial 0 case — you would then miss counting 0 when left = 0.

Solution: Be deliberate about whether 0 should be included. If the problem guarantees left >= 1, starting from base = 1 is safe and slightly faster. Otherwise, keep base starting at 0 (as the current code does) so that 0 is correctly considered.

# Safe when left can be 0: start from base = 0 (current approach)
for base in count():
    power = base ** k
    if power > right:
        break
    if left <= power <= right:
        answer += 1

Pitfall 2: Infinite Loop When `right` Is Extremely Large or `base = 1` Stalls Progress

When k >= 2, base ** k grows quickly, so the break condition terminates the loop reliably. But consider edge inputs:

If you mistakenly handle k = 1 inside the same loop (instead of the early return), then power = base ** 1 = base grows by only 1 each iteration. For a large right (e.g., 10^9), this loop runs a billion times — effectively a performance trap, not a true infinite loop, but unacceptably slow.

Solution: Always keep the k == 1 special case as an O(1) early return (as the code does). Never let k = 1 fall through into the enumeration loop.

if k == 1:
    return right - left + 1  # O(1), avoids the slow linear scan

Pitfall 3: Integer Overflow in Other Languages

In Python, integers have arbitrary precision, so base ** k never overflows. But if you port this solution to Java, C++, or Go, computing base ** k can overflow a 32-bit or 64-bit integer before the power > right check executes, producing a negative or wrapped-around value. This can either cause the loop never to break or skip valid counts.

Solution: In fixed-width languages, guard against overflow by checking before multiplying, or by computing the power in a wider type and comparing against right carefully.

// C++ example: detect overflow during exponentiation
long long power = 1;
bool overflow = false;
for (int i = 0; i < k; i++) {
    if (power > right / base) {   // would overflow / exceed right
        overflow = true;
        break;
    }
    power *= base;
}
if (overflow || power > right) break;

Pitfall 4: Using `pow()` with Floating-Point Precision Errors

A tempting alternative is to compute the integer kth root directly using round(right ** (1/k)) and round(left ** (1/k)) to get the answer in O(1). While faster, floating-point inaccuracies can produce off-by-one errors. For example, round(1000 ** (1/3)) might yield 9 instead of 10 due to precision loss.

Solution: If you opt for the math-based approach, always verify the result with integer arithmetic by adjusting the candidate root up or down:

def integer_kth_root(n, k):
    if n < 0:
        return -1
    r = int(round(n ** (1.0 / k)))
    # Adjust for floating-point error
    while r ** k > n:
        r -= 1
    while (r + 1) ** k <= n:
        r += 1
    return r

This keeps the O(1)-ish performance benefit while guaranteeing correctness.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: