Kth root problem

#1

please see output wrong for n>10^5
here is the code:https://ide.codingblocks.com/s/157144

#2

In the input n = 1000000000000000 and k = 10
The first mid value that we get is (0 + 1000000000000000)/2 = 500000000000000
and 500000000000000^10 is a very very big number that cannot be stored in a variable of type long long int.

1 Like
#3

So what to do sir for this case? Is my approach wrong??

#4

We can try by first finding an upper bound to the value of x so that x^k does not exceed 2^55 (a random number greater than 10^15)

Let the upper bound be z
So now to find the value of z Let
z^k = 2^55
Take log of base 2 on both sides to get
log2(z^k) = log2(2^55)
k*log2(z) = 55
log2(z) = 55/k
z = 2^(55/k) (Note:- take ceil of 55/k)

Example if k = 10
then z = 2^(55/10) = 2^6 = 64

first find this value and then apply binary search on a range from 0 to z to get the value of x

2 Likes