Skip to main content
Talentd

Count K-th Roots in a Range - Solution & Explanation

MediumMathBinary Search7 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given a range [L, R] and an integer k, count how many integers x exist such that x^k lies within the range. In other words, how many perfect k-th powers fall between L and R.

Approach 1: Brute Force Enumeration (O((R-L) * log k) time, O(1) space)

Iterate through every number in the range [L, R] and check whether it is a perfect k-th power. For each number n, compute its k-th root using floating-point math or repeated multiplication and verify if the root raised back to k equals n. This works but quickly becomes impractical when the range is large. The algorithm spends most of its time scanning numbers that cannot possibly be perfect powers.

Approach 2: Mathematical Root Boundaries (O(1) time, O(1) space)

A better observation: instead of checking numbers in the range, count the integers whose k-th power lands inside the range. If x^k must satisfy L ≤ x^k ≤ R, then x must satisfy L^(1/k) ≤ x ≤ R^(1/k). Compute low = ceil(L^(1/k)) and high = floor(R^(1/k)). The number of valid integers is max(0, high - low + 1). This converts a potentially massive iteration into a constant-time math calculation.

Approach 3: Binary Search for Integer k-th Roots (O(log R) time, O(1) space)

Floating point roots may introduce precision issues for large numbers. A safer method is to compute integer k-th roots using binary search. Search for the largest integer whose k-th power is ≤ R, and the largest integer whose k-th power is < L. Subtract the two counts to get the number of valid bases. This approach guarantees correctness even when L and R approach 64‑bit limits.

These strategies rely on recognizing that the problem is fundamentally mathematical rather than iterative. Understanding exponent growth drastically shrinks the search space.

Recommended for interviews: The mathematical boundary approach combined with careful integer root handling is the expected solution. Mention the brute force method first to demonstrate baseline reasoning, then transition to the optimized formula. Interviewers often expect candidates to recognize the x^k inequality transformation and optionally implement a safe root calculation using math or binary search.

Solution

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

Otherwise, we enumerate integers x, compute y = x^k. If y exceeds r, we stop enumeration. If y is within the range [l, r], we increment the answer by 1.

The time complexity is O(r^{1/k} cdot k), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO((R-L) * log k)O(1)Small ranges or initial reasoning during interviews
Mathematical Root BoundsO(1)O(1)General case when floating-point precision is acceptable
Binary Search k-th RootO(log R)O(1)Large integers or when exact integer arithmetic is required

Video Solution

Count K-th Roots in a Range | LeetCode 3932 | Weekly Contest 502 | Java | Developer Coder • Developer Coder • 558 views views

Watch 5 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Count K-th Roots in a Range with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer