Skip to content

3932. Count K-th Roots in a Range

Description

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

Solutions

Solution 1: Enumeration

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countKthRoots(self, l: int, r: int, k: int) -> int:
        if k == 1:
            return r - l + 1
        ans = 0
        for x in count():
            y = x**k
            if y > r:
                break
            if l <= y <= r:
                ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countKthRoots(int l, int r, int k) {
        if (k == 1) {
            return r - l + 1;
        }
        int ans = 0;
        for (int x = 0;; x++) {
            long y = 1;
            for (int i = 0; i < k; i++) {
                y *= x;
                if (y > r) {
                    break;
                }
            }
            if (y > r) {
                break;
            }
            if (l <= y && y <= r) {
                ans++;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int countKthRoots(int l, int r, int k) {
        if (k == 1) {
            return r - l + 1;
        }
        int ans = 0;
        for (int x = 0;; x++) {
            long long y = 1;
            for (int i = 0; i < k; i++) {
                y *= x;
                if (y > r) {
                    break;
                }
            }
            if (y > r) {
                break;
            }
            if (l <= y && y <= r) {
                ans++;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func countKthRoots(l int, r int, k int) int {
    if k == 1 {
        return r - l + 1
    }
    ans := 0
    for x := 0; ; x++ {
        y := 1
        for i := 0; i < k; i++ {
            y *= x
            if y > r {
                break
            }
        }
        if y > r {
            break
        }
        if l <= y && y <= r {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countKthRoots(l: number, r: number, k: number): number {
    if (k === 1) {
        return r - l + 1;
    }
    let ans = 0;
    for (let x = 0; ; x++) {
        let y = 1;
        for (let i = 0; i < k; i++) {
            y *= x;
            if (y > r) {
                break;
            }
        }
        if (y > r) {
            break;
        }
        if (l <= y && y <= r) {
            ans++;
        }
    }
    return ans;
}

Comments