count-k-th-roots-in-a-range

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given three integers <code>l</code>, <code>r</code>, and <code>k</code>.

An integer <code>y</code> is said to be a perfect kth power if there exists an integer <code>x</code> such that <code>y = xk</code>.

Return the number of integers <code>y</code> in the range <code>[l, r]</code> (inclusive) that are perfect kth powers.

&nbsp;
Example 1:

<div class="example-block">
Input: l = 1, r = 9, k = 3

Output: 2

Explanation:
The perfect cubes in the range <code>[1, 9]</code> are:

<ul>
	<li><code>1 = 13</code></li>
	<li><code>8 = 23</code></li>
</ul>
Hence, the answer is 2.</div>

Example 2:

<div class="example-block">
Input: l = 8, r = 30, k = 2

Output: 3

Explanation:
The perfect squares in the range <code>[8, 30]</code> are:

<ul>
	<li><code>9 = 32</code></li>
	<li><code>16 = 42</code></li>
	<li><code>25 = 52</code></li>
</ul>
Hence, the answer is 3.</div>

&nbsp;
Constraints:

<ul>
	<li><code>0 &lt;= l &lt;= r &lt;= 109</code></li>
	<li><code>1 &lt;= k &lt;= 30</code></li>
</ul>