BS-11. Find the Nth root of an Integer
HTML-код
- Опубликовано: 2 окт 2024
- Problem Link: bit.ly/3oWhSkW
Notes/C++/Java/Python codes: takeuforward.o...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/take...
0:00 Introduction of Course
The edge case of overflow was amazing. Thank you for such amazing content. Consider completing the series we are eagerly waiting.
this is a hidden gem playlist in entire youtube
understood
Thank you striver for such an amazing explanation.
It's better to keep high as m/n. We can reduce the number of checks using this.
can we use power func --- pow(mid,n) ??? instead of writing different function??
Done, Here's my approach to this question:
long long binPower(int a,int b,int m){
long long ans=1;
long long temp=a;
while (b){
if (temp>m || ans*temp>m) return INT_MAX; // so that high moves to mid-1
if (b&1){
ans=1LL*ans*temp;
}
temp=1LL*temp*temp;
b>>=1;
}
return ans;
}
int NthRoot(int n, int m) {
int low=1;
int high=m;
int ans=0;
while (lowm) high=mid-1;
else low=mid+1;
}
return -1;
}
Handling the overflow case was amazing !! I didn't got that one
The most simplified explanation one could ever get!
wow explanation
Solved this too myself thnx ❤
consistency to gave such awesome videos makes u a good youtuber ...keep doing sir
oh i really see that coming....😂😂
public class Solution {
public static int NthRoot(int n, int m) {
int ans = -1;
int low = 1;
int high = m;
while(low m){
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ans;
}
}
suppose M=10^63-1;( max value of long long), and mid=10^63/2, now is mid
when you are modifying code for overflow, the T.C got changed to O(n*logm). How to do it in O(logn logm)?
Why can't we use pow(mid,n) to calculate power instead of writing an entire function in C++?
watch the video from 15:30 till end, it will cause overflow.
one workaround is to do pow(mid,1/n), take floor of it and check if it is same as the number (i mean to say if its a integer instead of some float value like 3.21 something)
understood
Understood:)
Can you share the code where you modify exponentiation function to handle overflow situation instead of naive multiplication function?
int NthRoot(int n, int m) {
int low=1;
int high=m;
int mid;
while(lowm)high=mid-1;
else low=mid+1;
}
return -1;
}
this code got submitted at once without any overflow
#include
using namespace std;
using ll = long long;
ll binExp(ll a, ll b, ll m){
// implementation of binary exponentiation without modulus
ll ans = 1;
while(b){
if (b % 2 == 1){
if (a 0) ans *= a; // ans may exceed m
else return m+1;
}
a *= a; // a may exceed m
b /= 2;
if (ans > m || ans < 0) return m+1; // may end up negative in case of overflow (not allowed constraints)
}
return ans;
}
int NthRoot(int n, int m) {
if (m == 1) return 1;
int lo = 1; int hi = m;
while(lo m) hi = mi-1;
else lo = mi+1;
}
return -1;
}
The implementation of the binary exponentiation without the help of modulo was one hell of a ride. Thanks for the insight.
#include
int NthRoot(int n, int m) {
// Write your code here.
int low = 1, high = m;
while(low
Understood! Super amazing explanation as always, thank you so so much for your effort!!
understood bhaiya, thank you for this tutorial
int NthRoot(int n, int m)
{
// Code here.
int low=1;
int high =m;
while(low m){
high = mid-1;
}else{
low = mid+1;
}
}
return -1;
}
T.C = O(logm * logn)
logm (for binary search) and logn(for calculations of power)
so isn't this better??
Your teaching style is awesome, I understand everything in detail
Can anyone please clear my doubt
what if in if() condtion in while loop I directly calculate power of mid like this if(pow(mid,n)==m)
will this genrate overflow ?
Striver can u please explain how can I do with binary exponentiation.....i tried still i am not able to figure it out....
i used following code:
long long ans=1;
while(n>0)
{
if(n%2==1)
{
ans=ans*mid
n=n-1;
}
else{
mid=mid*mid;
if(mid>m)
return 2;
n=n/2;
}
}
if(ans==m) return 1;
return 0;
This is using binary exponentiation. TC = O(log(m)*log(n)
class Solution{
public:
long long fun(long x, long long n, long long m){
long long ans =1;
while(n>0){
if(n%2==1){
ans=ans*x;
if(ans>m) return -1;
n--;
}
else{
x=x*x;
if(x>m) return -1;
n/=2;
}
}
}
int NthRoot(int n, int m)
{
long long low =0;
long long high =m;
while(low
int NthRoot(int n, int m)
{
long long l = 1, r = m;
if(n == 1) return m;
while(l
int NthRoot(int n, int m)
{
if (m == 0) {
return 0; // Special case: 0th root of 0 is 0
}
int low = 1;
int high = m;
int result = -1;
while (low m) {
high = mid - 1;
} else {
low = mid + 1;
result = mid; // Keep track of potential result
}
}
return result; // Return the last valid result found
} whats wrong with code ?
Can anyone explain why this code is not working
class Solution{
public:
int power(int i, int n, int m){
long long res = 1;
while(n){
if(n & 1) res = res * i;
if(res > m) return 2;
i = i * i;
n >>= 1;
}
if(res == m) return 1;
return 0;
}
int NthRoot(int n, int m){
int l = 1, h = m;
while(l
Understood,Thanks striver for this amazing video.
public class Solution {
public static int NthRoot(int n, int m) {
int low = 1;
int high = m;
while (low m) break;
}
if (val == m) {
return mid;
} else if (val > m) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
}
Was missing the overflow case. Thanks to this amazing video.
Sometimes I feel he is scolding me. But honestly this is one of the best playlist available on YT.
What will be the time complexity ? will it be nlogm where m is the number whose root needs to be calculated and it the given power? log m for BS and multiply it with n foe calculate power of every number am I right ?
@@VarshaSingh-hi2sb Yes correct, complexity will be O(n log (m))
@@VarshaSingh-hi2sb it feels lyk u are scolding 😅
understood
Understood
Root of any even num is always even and same goes with odd too. We should apply this concept too to reduce a bit of time complicity.
understood
understood
Time complexity for the optimal approach?....while handling overflow condition M
UnderStood!
kch number na aaye dimag me , 69 jroor ata h 😆
Understood
long start = 1;
long end = m;
while (start m / (Math.pow(mid, n - 1))) {
end = mid - 1;
} else if (mid < m / (Math.pow(mid, n - 1))) {
start = mid + 1;
} else {
return (int) mid;
}
}
return -1;
This also works.
what is the logic behind m / (Math.pow(mid, n - 1) ?
@@yashaggarwal6013 mid * mid**(n-1) = mid**n
to understand this video i lean power exp it take me 2 hrs to learn because of -ve power in leet code ,and at last striver solve this porblem by simple for loop.🤩🤩🤩🤩🤩🤩❤❤😥😥
instead of func can we use pow(mid,n)??
no at the end of the video bhaiya explained the case of 10 to the power 90 which will overflow so we use the function , if we use pow it will directly give 10 the power 90 which will overflow and we ll not get output
@@Sankhamit leetcode accepted the solution using pow
Understood Very Well!
Thank you Striver....Understood everything🙂
Understood
I have a doubt,instead of creating multiplication function,im simply using pow(mid,n) and im not having overflow
Is this fine?
is it working fine?? cause I was thinking of the same approach. but I think it can also lead to overflow. In which language you were doing this
I am your big fan because of your videos are well and explanation also
lets assume we need to find nth root of num, so if we set low=0, high=num/n, then the overflowing edge case can be avoided to some extent, as we know nth root cannot exceed num/n...
engineers and their obsession with the number 69😂😂😂😂😂😂😂😂
hahahahahah i was looking for this comment to see wheather someone else has also noticed this or its only me 🤣
bhaiyya in square root question we can minimize some iteration using high=n/2
a squreRoot of number always lies in 1 to num/2😄
Not some, only 1 iteration
Can't we use mid**n to check and then increase or decrease the low and high accordingly.
this way we don't have to use the function and no need of for loop also
understood🙃
understood
Edge case explained when mid^n > m then overfllow occurs
int func(int mid, int n, int m)
{
long long ans = 1;
for (int i = 1; i m)
{
return 2;
}
}
if (ans == m)
{
return 1;
} // return 1 if ans == m
return 0; // return 0 if ans < m
}
For example, let's say mid = 3, n = 2, and m = 8. During the loop, the value of ans will be calculated as follows:
ans = 1 * 3 = 3 (after the first iteration)
ans = 3 * 3 = 9 (after the second iteration)
At this point, ans (which is now 9) is greater than m (which is 8), and the function will return 2, indicating that 3^2 is greater than 8.
explaining the concepts excellent
why can't i keep like
for(int i = 1; i m) return 0;
res = res*mid;
// if(res > m) return 0;
}
It's giving wrong answer.
if mid=5 and m = 34 then
it will go like this
first iteration -> res(1)>m not true, res=1*5
second iteration -> res(5)>m not true, res=5*5
third iteration ->res(25)>m not true, res=5*5*5
so your if is not working correctly
@@HimanshuYadav-ry8tk thanks a lot
Why 69 as an example 😅?
💀
fantasy no.
++thanks
instead of the check func can we use inbuilt power func that will also work
Overflow case will be an issue
@@takeUforward Okay bhaiya
Dealing with the overflow case is too tricky. That's kind of thing is taughts you only
In python, it doesn't cause any issue with that code. But thanks for that edge case of c++.
Amazing Playlists
does anyone know where to use low
my implementation :-
typedef long long ll;
ll multiply(ll mid , int n,int m)
{
ll ans=1;
for(int i=1;im)
{
//to overcome the overflow bada ho gya to bas break kar do
break;
}
}
return ans;
}
int NthRoot(int n, int m)
{
if(n==1)
return m;
int low = 1;
int high = 1e5;
while(low
understood
i have a doubt this just failing the test case but not giving any error and if it not giving an error how can we suppose to find out the problem there has to be any trick or tips for this type of edge case
thanks you striver for.... easy explanation
understood bhaiya
Isnt the time complexity for this code is O(nlogm)
Last for today 😮
Understood 🙏🏻
Understood :)
understood:)
understood!
understood!
Understood.
UNDERSTOOD;
Understood😊
Understood!
understood!
Understoood
understood
UNDERSTOOD
understood
understood
understood
UnderStood
understood
Understood
understood
understood
Understood
understood
understood
understood
Understood
understood