Please help me with understanding the problem type

#1

I want to understand what theory is required to understand this problem

#2

Hi arvind,
Basically first come with a brute force approach to find greatest integer x, such that, x^k <= n using for loop.[Hint: use Math.pow(i,k) ]
It will give Time Limit Exceed,then we will discuss the right approach.

#3
#4

@radhagovinda008
Please try to take test cases as well.
Moreover your logic is slightly incorrect we need to find greatest such a number which follows
Math.pow(number,k)<=n Not the value of this Math.pow(number,k).
revert back after correcting your logic.

#5

x=(long) Math.pow(i, k);
if(x<=n)
max=x;
i tried to keep value less than “n” in max

#6

@radhagovinda008
You need to find an i such that i raised to power k is less than n.
We dont need to find maximum i raised to power k,which you are finding.

x=(long) Math.pow(i, k);
if(x<=n)
max=x;

Lets Dry Run your code snippet line by line you are storing val Math.pow(i,k) in variable x and in second line updating max variable. which isn’t required.
try to think a way that starting from i=1 we need to check every i raised to pow <=N and when this conditions holds false this i is our answer.
Hope this helps.
Revert back after correcting your logic.Thanks

#7

now it’s working but for one test case it’s giving time limit exceeded

#8

@radhagovinda008
Nice,As you have written the basic approach in which while loop is doing lot of operations which is having linear time complexity O(n).
Now try to think in terms of Binary Search to reduce the time complexity of your code.

#9

why do I need binary search??

#10

@radhagovinda008
As you are iterating for every i and going till N which makes a time complexity of O(n).
Do you know time complexity of Binary Search it’s log(n).
Here we are just searching for a max possible value of i which can be searched in less time using Binary Search.

#11

Please help me understanding it in more details.
the for loop from i=1 to N is for the purpose of getting the value i^k
and in that loop body only I am using greedy approach to store max value of i^k which is not >N
so where is the point of searching element??
and for binary search what should be my array?

#12

@radhagovinda008
if you clearly watch the Constraints given N can range upto 10^15.
Now assume a test case K=1 and N=10^15.Now your code will make roughly 10^15 calculations,hence will eventually give TLE.
Moreover,Binary Search needs only search space,It doesn’t require any array to be search within.
This problem demands you to use Binary Search to find i in the Search Space 1 to N.

#13

I am not getting your point

#14

Hi Arvind,
Let me try again,The basic brute force solution is loop from i=1 ,and when Math.pow(x,i) becomes greater than n,print the i.
First code this simple logic,and provide link here,then we will further optimise the code.

#15

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.