KTH root binary search

#1

Can you give me some test cases where my code is failing?

#2

In the question it is given that x^k <= n, you also need to save the answer in variable when the
pow(mid,k)<n.
Also for finding mid, use this way => mid = start + (end-start)/2
because the simple (start+end)/2 way will cause problem when value of start or mid is LONG_LONG_MAX_VALUE.

I hope now you have got your answer

#3

I only did the first change suggested by you and my solution got accepted.
What were you trying to say here “because the simple (start+end)/2 way will cause problem when value of start or mid is LONG_LONG_MAX_VALUE”, can you elaborate more?

#4

let say start = 10^18 and end = 10^18 (here i am considering 10^18 as upper limit of long long int but its not the exact one).
so when you do (start + end) = 2 * 10^18 which is more than upper limit so it will be some negative value (as you know what happens when out of range) so mid value will something else and it will give Wrong Answer.
I think this type of test cases are not included in it the problem thats why it passes without doing this.

1 Like
#5

ok man, I got your point. So it is safer to use the other formula for finding mid in other problems?

1 Like
#6

ya right, otherwise you may keep debugging and not able to find it out.

#7

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.