Is Count K-th Roots in a Range easy or hard?

The difficulty is usually rated Medium because the brute force idea is simple but inefficient. The key step is recognizing the mathematical transformation from x^k range constraints to root boundaries.

Count K-th Roots in a Range Python/Java solution

A typical solution computes low = ceil(L ** (1/k)) and high = floor(R ** (1/k)) in Python, or uses Math.pow in Java. For strict accuracy with large numbers, implement a binary search that finds the largest integer whose k-th power is within the bound.

How to solve Count K-th Roots in a Range in O(1)?

Transform the inequality L ≤ x^k ≤ R into root bounds. Calculate the smallest integer x such that x^k ≥ L and the largest integer x such that x^k ≤ R. The difference between these bounds gives the count of valid integers in constant time.

What is the best approach for Count K-th Roots in a Range?

The most efficient approach converts the constraint L ≤ x^k ≤ R into root boundaries. Compute low = ceil(L^(1/k)) and high = floor(R^(1/k)), then return max(0, high − low + 1). This reduces the problem to constant-time math instead of scanning the entire range.

Is Count K-th Roots in a Range asked at Google/Amazon/Meta?

Problems involving perfect powers, root bounds, and integer exponent ranges appear in interviews at companies like Google, Amazon, and Meta. They test mathematical reasoning and the ability to reduce brute force enumeration using inequalities and logarithmic search.

What data structure is used in Count K-th Roots in a Range?

The problem mainly relies on mathematical computation rather than complex data structures. Some implementations use binary search over integers to compute precise k-th roots, which requires only basic variables and arithmetic operations.

What is the time complexity of Count K-th Roots in a Range?

The optimal mathematical approach runs in O(1) time and O(1) space because it only computes two k-th roots and performs simple arithmetic. If integer roots are computed using binary search, the complexity becomes O(log R) time with constant space.

3932. Count K-th Roots in a Range - Practice Online

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.

Example 1:

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

Output: 2

Explanation:

The perfect cubes in the range [1, 9] are:

1 = 1³
8 = 2³

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 = 3²
16 = 4²
25 = 5²

Hence, the answer is 3.

Constraints:

0 <= l <= r <= 10⁹
1 <= k <= 30