LeetCode-in-Java

3932. Count K-th Roots in a Range

Medium

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 = xk.

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 = 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

Solution

public class Solution {
    public int countKthRoots(int l, int r, int k) {
        if (k == 1) {
            return r - l + 1;
        }
        int ans = 0;
        int start = 0;
        int pow = (int) Math.pow(start, k);
        while (l > pow) {
            start++;
            pow = (int) Math.pow(start, k);
        }
        while (pow <= r) {
            start++;
            pow = (int) Math.pow(start, k);
            ans++;
        }
        return ans;
    }
}

This site is open source. Improve this page.