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

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.