Welcome to Subscribe On Youtube

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

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}

  • 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;
}

All Problems

All Solutions