pls guide me through
rest of the solution
Kth root problem
we have to find greatest x such that x^k <= n, so we will apply binary search on x to find solution. we pass low (n) and high (k) to binary search. Now, we will calculate mid using low and high i.e (low + high + 1)/2 and we’ll check if mid ^ k <= n. If it is greater than n, then the solution must lie between low and mid-1 so mid-1 becomes new high. If it is smaller than or equal n then solution must lie between mid and high so mid becomes new low and this thing will go on till low remains less than high when it becomes equals or greater than the answer will low itself.
Few Mistakes you made in your code:
- you don’t need to calculate power using modular exponentiation, multiply iteratively and if intermediate product exceeds n return false else true
- include condition in binary_search to return n when k == 1
Here is the code with mistakes rectified: https://ide.codingblocks.com/s/171243
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.