Kth root:code is not working for test cases

#1

Please let me know the problem in my code, it gives correct output for sample input, but does not pass any test casehttps://ide.codingblocks.com/s/222649

#2

@56amrut.bhokardankar,

You need to modify your approach a little bit.

We will aplly binary search in this problem. For every possible mid obtained by using binary search we will check of it is the best suitable candidate or not for becoming the Kth root and then we reduce the search space of the binary search according to the mid value. If mid^k is greater than N then we will find the best suitable value from left to mid-1 otherwise we will find much larger value by finding it from mid+1 to right.

#3

@56amrut.bhokardankar,
What error are you facing?

#4

why you have done mid=(hi+lo+1)/2 instead of (hi +lo)/2 https://ide.codingblocks.com/s/222730

#5

also why hi = 1000000;?

#6

Also please tell why the code given below is not passing all the test cases(i used this approach earlier )?
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
if(t<1||t>10)return;
while(t>0)
{
long n=sc.nextLong();
if(n>1000000000000000l||n<1)return;
long k=sc.nextLong();
if(k>10000||k<1)return;
double x=(double) n;
double y=(double) k;
//double t=Math.round(Math.log(x));
double p=Math.exp(Math.log(x)/y);
int v = (int)p;
System.out.println(v);
t–;
}
}
}

#7

@56amrut.bhokardankar,

If lo + hi is an odd number, it will set mid to an index before the actual mid. lo is 1, hi is 10, mid will be 5 if we don’t add 1.

initially hi = 10^6, and k = 10, n = 1000000000000000

Now we keep multiplying mid until it either exceeds n or we multiply it k number of times. as seen in this for loop ( for (int i = 1; i <= k; i++) )

Now initially:
mid is 5001 (not our final answer)
lo is 1
hi is 5000

After that we half mid by (lo+hi+1)/2, mid becomes: 2501. But again this is not our final answer. Now, lo is 1 and hi is 2500.
And we check until we get our answer as 31.

#8

@56amrut.bhokardankar,
your code gives wrong answer for the test case:
1
1000000000000 4
Your output: 999
Correct Output: 1000