Count perfect power of K in a range [L, R]
Given three integers L, R, and K, the task is to find the count of the number of integers between L to R, which are perfect power of K. That is the number of integers that are in the form of aK, where a can be any number.
Examples:
Input: L = 3, R = 16, K = 3
Output: 1
Explanation:
There is only one integer between 3 to 16 which is in the for aK which is 8.Input: L = 7, R = 18, K = 2
Output: 2
Explanation:
There are two such numbers that are in the form of aK and are in the range of 7 to 18 which is 9 and 16.
Approach: The idea is to find the Kth root of the L and R respectively, where Kth root of a number N is a real number that gives N, when we raise it to integer power N. Then the count of integers which are the power of K in the range L and R can be defined as –
Count = ( floor(Kthroot(R)) - ceil(Kthroot(L)) + 1 )
Kth root of a number N can be calculated using Newton’s Formulae, where ith iteration can be calculated using the below formulae –
x(i + 1) = (1 / K) * ((K – 1) * x(i) + N / x(i) ^ (N – 1))
Below is the implementation of the above approach:
C++
// C++ implementation to find the // count of numbers those are // powers of K in range L to R #include <bits/stdc++.h> using namespace std; // Function to find the // Nth root of the number double nthRoot( int A, int N) { // initially guessing a random // number between 0 to 9 double xPre = rand () % 10; // Smaller eps, // denotes more accuracy double eps = 1e-3; // Initializing difference between two // roots by INT_MAX double delX = INT_MAX; // xK denotes // current value of x double xK; // loop until we reach desired accuracy while (delX > eps) { // calculating current value // from previous value xK = ((N - 1.0) * xPre + ( double )A / pow (xPre, N - 1)) / ( double )N; delX = abs (xK - xPre); xPre = xK; } return xK; } // Function to count the perfect // powers of K in range L to R int countPowers( int a, int b, int k) { return ( floor (nthRoot(b, k)) - ceil (nthRoot(a, k)) + 1); } // Driver code int main() { int a = 7, b = 28, k = 2; cout << "Count of Powers is " << countPowers(a, b, k); return 0; } |
Java
// Java implementation to find the // count of numbers those are // powers of K in range L to R class GFG{ // Function to find the // Nth root of the number static double nthRoot( int A, int N) { // initially guessing a random // number between 0 to 9 double xPre = Math.random()* 10 % 10 ; // Smaller eps, // denotes more accuracy double eps = 1e- 3 ; // Initializing difference between two // roots by Integer.MAX_VALUE double delX = Integer.MAX_VALUE; // xK denotes // current value of x double xK = 0 ; // loop until we reach desired accuracy while (delX > eps) { // calculating current value // from previous value xK = ((N - 1.0 ) * xPre + ( double )A / Math.pow(xPre, N - 1 )) / ( double )N; delX = Math.abs(xK - xPre); xPre = xK; } return xK; } // Function to count the perfect // powers of K in range L to R static int countPowers( int a, int b, int k) { return ( int ) (Math.floor(nthRoot(b, k)) - Math.ceil(nthRoot(a, k)) + 1 ); } // Driver code public static void main(String[] args) { int a = 7 , b = 28 , k = 2 ; System.out.print( "Count of Powers is " + countPowers(a, b, k)); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 implementation to find the # count of numbers those are # powers of K in range L to R import sys from math import pow ,ceil,floor import random # Function to find the # Nth root of the number def nthRoot(A,N): # initially guessing a random # number between 0 to 9 xPre = (random.randint( 0 , 9 )) % 10 # Smaller eps, # denotes more accuracy eps = 1e - 3 # Initializing difference between two # roots by INT_MAX delX = sys.maxsize # xK denotes # current value of x # loo3p until we reach desired accuracy while (delX > eps): # calculating current value # from previous value xK = ((N - 1.0 ) * xPre + A / pow (xPre, N - 1 )) / N delX = abs (xK - xPre) xPre = xK return xK # Function to count the perfect # powers of K in range L to R def countPowers(a, b, k): return (floor(nthRoot(b, k)) - ceil(nthRoot(a, k)) + 1 ) # Driver code if __name__ = = '__main__' : a = 7 b = 28 k = 2 print ( "Count of Powers is" ,countPowers(a, b, k)) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation to find the // count of numbers those are // powers of K in range L to R using System; using System.Collections.Generic; public class GFG{ // Function to find the // Nth root of the number static double nthRoot( int A, int N) { // initially guessing a random // number between 0 to 9 Random r = new Random(); double xPre = r.Next(0,9); // Smaller eps, // denotes more accuracy double eps = 1e-3; // Initializing difference between two // roots by int.MaxValue double delX = int .MaxValue; // xK denotes // current value of x double xK = 0; // loop until we reach desired accuracy while (delX > eps) { // calculating current value // from previous value xK = ((N - 1.0) * xPre + ( double )A / Math.Pow(xPre, N - 1)) / ( double )N; delX = Math.Abs(xK - xPre); xPre = xK; } return xK; } // Function to count the perfect // powers of K in range L to R static int countPowers( int a, int b, int k) { return ( int ) (Math.Floor(nthRoot(b, k)) - Math.Ceiling(nthRoot(a, k)) + 1); } // Driver code public static void Main(String[] args) { int a = 7, b = 28, k = 2; Console.Write( "Count of Powers is " + countPowers(a, b, k)); } } // This code is contributed by umadevi9616 |
Javascript
<script> // JavaScript implementation to find the // count of numbers those are // powers of K in range L to R // Function to find the // Nth root of the number function nthRoot(A, N) { // initially guessing a random // number between 0 to 9 var xPre = Math.random() % 10; // Smaller eps, // denotes more accuracy var eps = 0.001; // Initializing difference between two // roots by INT_MAX var delX = 1000000000; // xK denotes // current value of x var xK; // loop until we reach desired accuracy while (delX > eps) { // calculating current value // from previous value xK = ((N - 1.0) * xPre + A / Math.pow(xPre, N - 1)) / N; delX = Math.abs(xK - xPre); xPre = xK; } return xK; } // Function to count the perfect // powers of K in range L to R function countPowers(a, b, k) { return (Math.floor(nthRoot(b, k)) - Math.ceil(nthRoot(a, k)) + 1); } // Driver code var a = 7, b = 28, k = 2; document.write( "Count of Powers is " + countPowers(a, b, k)); </script> |
Count of Powers is 3
Performance Analysis:
- Time Complexity: As in the above approach, there are two function calls for finding Nth root of the number which takes O(logN) time, Hence the Time Complexity will be O(logN).
- Space Complexity: As in the above approach, there is no extra space used, Hence the space complexity will be O(1).
Contact Us