the given code covers a edge case you may having in leetcode, explaination:the integer.minvalue is can't be converted to positive even if you convert it using abs still it stays the same.so what i am doing here is just checking if n is a minvalue then i am +1 with this so that it can come to the positive bound then we can be able to convert it to positive and i am also multiplying the x with ans so that we utilized the 1 class Solution { public double myPow(double x, int n) { /*double ans=1; boolean nsign=n
For LEETCODE : (Covering all the Corner Cases) class Solution { public double myPow(double x, int n) { double ans = 1; double oriNum = n; if(x == 0 || x == 1) return x; if(n < 0){ x = 1/x; n = -(n+1); //for Integer.MIN_VALUE ans = ans * x; }
while(n > 0) { if(n % 2 == 1) { ans = ans * x; n = n-1; } else { n = n/2; x = x * x; } } return ans; } }
for overflow scenario's just use an unsigned right shift n>>>=1 is equal to n/2. why unsigned not signed right shift let say in case of number like -2147483648 if u take an abs it will -2147483648 same number again and then if you divide by 2 or signed right shift this number will be going forever negative, reason in signed right shift it replaces left vacated bits with 1 eventually you number will become -1111111....11111 in form of bits and forever loop, in this in case of unsigned right shift >>> it will fill vacated left values to zero so it will never overflow and eventually become 0 all the other code keep same make n = n/2 to n>>>=1 you will cover all cases :)
wrong solution if n is negative .Even if we store n in m .n does not doing to while loop condition becomes false for every negative n number and note the answer will be always 1 for n
not sure if this will help someone, but i was trying to figure out why are we saving to result ? when we are squaring the input x ? Because order of operations matter! ( PEMDAS and/or BODMAS ) binary exponentiation: repeatedly square the base, and half the exponent x^n even exp = (x*x)^n/2 odd exp = x * (x*x)^(n-1)/2 [ we could do n/2 because int division will round down anyways ] x = 2; n = 10 x | n ---------------------- 2*2 | 5 ---------------------- 4 | 5 4*(4*4) | 5/2 4 * 16 | 2 you might be tempted to perform 4 * 16 and then solve for 16^2 - but this is the catch! - order of operations matter - exponent / power comes first before multiplication - therefore! save the current base into res to perform multiplication LATER and handle exponent first! ------------------------------------------------ 4 * (16*16) | 2/2 4 * 256 | 1 ------------------------------------------------ 256^1 = 256 and now we can multiply remaining terms that got left over when exp was odd - 4 * 256 = 1024
Here is the Code for the negative power : public static double pow(int x, int n) { // Handle negative exponent if (n < 0) { // Calculate positive exponent result return 1.0 / pow(x, -n); }
int result = 1; while (n > 0) { if (n % 2 == 1) { result *= x; n--; } else { n /= 2; x *= x; } }
Solve as if n is positive, in the end if it was negative just do reciprocal class Solution { public: double myPow(double x, int n) { double ans=1.0; long nn=n; if(nn0){ if(nn%2==1){ ans*=x; nn-=1; } else{ x*=x; nn/=2; } } if(n
Instead of int m= abs(n) just take long m= abs(n) because when n= int_min then it's absolute value is 2^31 which is outside the range of int therefore use long to get the correct absolute value of int min
Here is the Code for the negative power : public static double pow(int x, int n) { // Handle negative exponent if (n < 0) { // Calculate positive exponent result return 1.0 / pow(x, -n); }
int result = 1; while (n > 0) { if (n % 2 == 1) { result *= x; n--; } else { n /= 2; x *= x; } }
// for posititve/negative powers public static double exponent(int x, int n) { double ans = 1; int m = n; if(n 0) { if (n % 2 == 1) { ans = ans * x; n = n - 1; } else { n = n / 2; x = x * x; } } if(m
Everyone , This famous even odd story is COMPLETELY WRONG. You can see the original paper on fast exponentiation to get actual understanding of why we store the accumulated number into result. In case of odd , why don't we multiply with single instance of number instead of accumultated number
This man is the top person in youtube to provide high quality content
I'm improving my logical thinking for problem solving by your teaching only.
class Solution {
public:
double myPow(double x, int n) {
int pow = abs(n);
double ans = 1;
while(pow > 0)
{
if(pow %2 == 0)
{
x=x*x;
pow /=2;
}
else
{
ans *=x;
pow = pow -1;
}
}
if(n < 0)
ans = 1/ans;
return ans;
}
};
the given code covers a edge case you may having in leetcode,
explaination:the integer.minvalue is can't be converted to positive even if you convert it using abs still it stays the same.so what i am doing here is just checking if n is a minvalue then i am +1 with this so that it can come to the positive bound then we can be able to convert it to positive and i am also multiplying the x with ans so that we utilized the 1
class Solution {
public double myPow(double x, int n) {
/*double ans=1;
boolean nsign=n
please also complete String Playlist.(This topic is more import for third college placement and it is more demanding topic for all guys.
Brother please next string playlist if possible 🙂
For LEETCODE : (Covering all the Corner Cases)
class Solution {
public double myPow(double x, int n) {
double ans = 1;
double oriNum = n;
if(x == 0 || x == 1) return x;
if(n < 0){
x = 1/x;
n = -(n+1); //for Integer.MIN_VALUE
ans = ans * x;
}
while(n > 0) {
if(n % 2 == 1) {
ans = ans * x;
n = n-1;
}
else {
n = n/2;
x = x * x;
}
}
return ans;
}
}
int a,x; // a is base and x is power
cin>>a>>x;
int ans =1;
while(x>0){
if(x&1)ans = ans*a;
a = a*a;
x>>=1;
}
cout
UNDERSTOOD....Thank You So Much for this wonderful video................🙏🏻🙏🏻🙏🏻🙏🏻
for overflow scenario's just use an unsigned right shift n>>>=1 is equal to n/2. why unsigned not signed right shift let say in case of number like -2147483648 if u take an abs it will -2147483648 same number again and then if you divide by 2 or signed right shift this number will be going forever negative, reason in signed right shift it replaces left vacated bits with 1 eventually you number will become -1111111....11111 in form of bits and forever loop, in this in case of unsigned right shift >>> it will fill vacated left values to zero so it will never overflow and eventually become 0 all the other code keep same make n = n/2 to n>>>=1 you will cover all cases :)
Then also use n&1 to determine odd
wrong solution if n is negative .Even if we store n in m .n does not doing to while loop condition becomes false for every negative n number
and note the answer will be always 1 for n
not sure if this will help someone, but i was trying to figure out why are we saving to result ? when we are squaring the input x ?
Because order of operations matter! ( PEMDAS and/or BODMAS )
binary exponentiation: repeatedly square the base, and half the exponent
x^n
even exp = (x*x)^n/2
odd exp = x * (x*x)^(n-1)/2 [ we could do n/2 because int division will round down anyways ]
x = 2; n = 10
x | n
----------------------
2*2 | 5
----------------------
4 | 5
4*(4*4) | 5/2
4 * 16 | 2
you might be tempted to perform 4 * 16 and then solve for 16^2
- but this is the catch!
- order of operations matter
- exponent / power comes first before multiplication
- therefore! save the current base into res to perform multiplication LATER and handle exponent first!
------------------------------------------------
4 * (16*16) | 2/2
4 * 256 | 1
------------------------------------------------
256^1 = 256
and now we can multiply remaining terms that got left over when exp was odd
- 4 * 256 = 1024
Thanks for the explanation 🎉
Here is the Code for the negative power : public static double pow(int x, int n) {
// Handle negative exponent
if (n < 0) {
// Calculate positive exponent result
return 1.0 / pow(x, -n);
}
int result = 1;
while (n > 0) {
if (n % 2 == 1) {
result *= x;
n--;
} else {
n /= 2;
x *= x;
}
}
return result;
}
x and result should be double too
Don't understand when the number is already negative so why are you putting it in the function again.
Understood ❤
Cover all edge cases
int tempN = n;
long N=abs(n);
double ans=1;
while(N!=0){
if(N%2==1){
N=N-1;
ans=ans*x;
}
else{
x=x*x;
N=N/2;
}
}
if(tempN
I have a small doubt, why does the last approach work, if someone can provide the intitution it will be super helpful.
Solve as if n is positive, in the end if it was negative just do reciprocal
class Solution {
public:
double myPow(double x, int n) {
double ans=1.0;
long nn=n;
if(nn0){
if(nn%2==1){
ans*=x;
nn-=1;
}
else{
x*=x;
nn/=2;
}
}
if(n
Thank_You✨
understood!
After watch 10 problems in placement series First time i write a code without seeing a pseudo code for this problem😅
Can you discuss about corner case
@striver Code will not work for negative power! BTW Thanks sir for the video❤
how to handle n = INT_MIN case
Instead of int m= abs(n) just take long m= abs(n) because when n= int_min then it's absolute value is 2^31 which is outside the range of int therefore use long to get the correct absolute value of int min
understood :)
understood
Code for Negative powers is not running.please help
yes because our while will never run because n is negative so our code will simply return 1/ ans (which is 1);
@@AkshitChaudhary-vx8iw how can we fix it?
@@deepalikumari5319 return 1 / pow(x, -n)
Bhai code kaha hai striver A - Z sheet mein lec 4 mein toh nhi dikh raha please batado
Here is the Code for the negative power : public static double pow(int x, int n) {
// Handle negative exponent
if (n < 0) {
// Calculate positive exponent result
return 1.0 / pow(x, -n);
}
int result = 1;
while (n > 0) {
if (n % 2 == 1) {
result *= x;
n--;
} else {
n /= 2;
x *= x;
}
}
return result;
}
Understood
Bhai wahi if negative interger h to -2147 ..... P positive krne p int flow hora
❤❤
// for posititve/negative powers
public static double exponent(int x, int n) {
double ans = 1;
int m = n;
if(n 0) {
if (n % 2 == 1) {
ans = ans * x;
n = n - 1;
} else {
n = n / 2;
x = x * x;
}
}
if(m
bro isme int overflow hoga if we multiply n*-1
@@ryuu5768 That is for converting the power to positive.
@@hritikminmuley1397 hn but wo out of int limit hojyega for a test case for n=-214........ Something
US
Everyone , This famous even odd story is COMPLETELY WRONG. You can see the original paper on fast exponentiation to get actual understanding of why we store the accumulated number into result. In case of odd , why don't we multiply with single instance of number instead of accumultated number
Understood
understood
understood
understood
understood