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

Thinking

\(r\le 10^9\), so we cannot walk every integer in the interval. Perfect \(k\)-th powers are the values \(x^k\) with \(l\le x^k\le r\).

When \(k=1\) the answer is the interval length. Otherwise \(x\) is at most about \(r^{1/k}\); compute \(y=x^k\) for \(x=0,1,2,\ldots\), stop past \(r\), and count hits in \([l,r]\).

The enumeration shrinks quickly as \(k\) grows, which covers \(k\le 30\).

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