Kth root problem

#1

You are given two integers n and k. Find the greatest integer x, such that, x^k <= n
sir i couldnt understand it…

#2

@YASHMATHURIA123
let suppose n is 16 and k is 2.
so if we put x=2, in x^k <=n then it means => 2^2 <= 16 i.e. 4<=16 , which is true.
but we need to find maximum x, so try for x=3 => 3^2 <= 16 i.e. 9<=16 , which is also true.
now take x=4, 4^2 <= 16 i.e. 16<=16, true.
now if we take x=5 then it will be false.

So x=4 is the answer in this case.

I hope you got it now.

1 Like
#3

sir mere is code m galat kya hai yeh 10^6 powert k liye work nahi kar raha hai

#include
#include<math.h>
using namespace std;
int main()
{
long long int n;
long long int k;
cin>>n;
cin>>k;
long long int start=1;
long long int end=n;
long long int mid;
long long int d=0;
while(start<=end)
{
mid=(start+end)/2;
long long int x=pow(mid,k);
if(x<=n)
{
d=mid;
start=mid+1;
}
else if(x>n)
{
end=mid-1;
}
}
cout<<d;
}

#4

sir mere is code m galat kya hai yeh 10^6 k liya run anhi kar raha hai

#5

@YASHMATHURIA123
lets suppose input n is 10^10 and k is 100. then your power function will try to calculate pow(mid, 100) and here mid = (1 + 10^10)/2; which is so big that power can’t be store in a variable.

So try to do it without using pow() function.
One thing we know is k <=10^4, so you can try to find it power linearly by your writing a code. so that it can never cross the limit of n.

1 Like
#6

@YASHMATHURIA123
if you have got the idea of what to do then its great
otherwise please have a look at this code https://ide.codingblocks.com/s/238486 (i have commented it properly for better explanation).

Feel free to ask if you don’t understand. Also let me know if you are able to solve it now.

1 Like
#7

@YASHMATHURIA123 please mark the doubt as resolved.

1 Like