slight correction in brute force:- when we linearly traverse we also need to check weather the number of set bits in that number is equal to set bits in num2 and also gives the minimal xor with num1, (great soln)
If the question is why the `while N {...}` becomes logN (instead of N) then the answer is -- any positive integer N has a maximum of logN + 1 bits in its binary representation (in order to convert a decimal number to binary we do N >> 1 or in other words we divide the problem space into half). The expression (N & (N - 1)) effectively removes one set bit (1) from the binary representation of N in each iteration. Combining both the arguments, the number of set bits in a number, which is at most logN + 1 for a number N. Thus the loop is guaranteed to run for almost logN times. Example - say n is 31 (11111) after first iteration - n=n&(n−1)=11111&11110=11110 (30) after second iteration n=n&(n−1)=11110&11101=11100 (28) after third iteration n=n&(n−1)=11100&11011=11000 (24) after fourth iteration n=n&(n−1)=11000&10111=10000 (16) after fifth iteration n&(n−1)=10000&01111=00000 (0) HTH!
slight correction in brute force:- when we linearly traverse we also need to check weather the number of set bits in that number is equal to set bits in num2 and also gives the minimal xor with num1, (great soln)
Thank you, great explanation!
Appreciate that! 🙏
Useful sir!!
nice 👌🏽
As usual, you did excellent teaching bro.😇
Appreciate the love! ❤️
Solid explanation, thank you!
Thanks
nice
Thanks :)
Brother how much is the cost of your program, I will try to join if I can afford?
Thanks for the solution and explanation ;)))))))))))))))))) !!!
Anytime! ❤️
THANKYOU SO MUCH Sir
welcome
Thank you sir :)
So nice of you
I didn't understand how counting the number of 1 was logN
If the question is why the `while N {...}` becomes logN (instead of N) then the answer is -- any positive integer N has a maximum of logN + 1 bits in its binary representation (in order to convert a decimal number to binary we do N >> 1 or in other words we divide the problem space into half). The expression (N & (N - 1)) effectively removes one set bit (1) from the binary representation of N in each iteration.
Combining both the arguments, the number of set bits in a number, which is at most logN + 1 for a number N. Thus the loop is guaranteed to run for almost logN times.
Example -
say n is 31 (11111)
after first iteration - n=n&(n−1)=11111&11110=11110 (30)
after second iteration n=n&(n−1)=11110&11101=11100 (28)
after third iteration n=n&(n−1)=11100&11011=11000 (24)
after fourth iteration n=n&(n−1)=11000&10111=10000 (16)
after fifth iteration n&(n−1)=10000&01111=00000 (0)
HTH!
I thought you were asking 😅
Nice detailed exampled 👌🏽
Good explanation
Thanks :)