Your explanation was super amazing. A couple of points: - The list of binary numbers you generated represents the gray code. - Sum of 2^k + 2^(k-1) + ... + 1 could be proved easily without the need to understand binary trees: S = 2^k + 2^(k-1) + ... + 1 ..... multiply by 2 on both sides 2S = 2^(k+1) + 2^k + 2^(k-1) + ... + 2 .... add 1 and subtract 1 on the right side 2S = 2^(k+1) + [2^k + 2^(k-1) + ... + 2 + 1] - 1 .... the part in square brackets is S, what we started off with 2S = 2^(k+1) + S - 1.... rearrange S = 2^(k+1) - 1 My solution: Time: O(log(b)) where b is the number of bits (e.g. 32 for int32), Space: O(1) Note: time is not to be confused with O(log(n)), it is O(log(log(n))). I tried to explain my intuition as clearly as I could. Please, bear with me. Thanks. Explanation and intuition of solution: I started off in the same way as you did, wrote out the binary numbers (converting n to 0) and found out that they were the gray codes. So, the minimum number of operations is equal to how we arrived at that gray code, which is basically just converting the gray code to its binary representation. E.g. if n=11, binary = 1011, we assume that this is the gray code (1011), and how did we arrive at this gray code is the binary number for this gray code = 1101 (13 in decimal). Q. Why did we assume 1011 as gray code? A. Because, if we trace back, converting this gray code to 0, this will give us the min operations (this is the property of gray code, that the adjacent codes differ by 1 bit). Q. Why will converting gray code to binary (or decimal) will give us the result? A. Because, initially, we assumed that given n is a gray code and not a binary, we want to reconstruct the original binary representation of n. Summary: The problem simplifies just to converting gray code to binary number. Enough with the talk. The code: num ^= num >> 16 num ^= num >> 8 num ^= num >> 4 num ^= num >> 2 num ^= num >> 1 return num The above solution is for 32-bit gray code to binary conversion. Following solution is adapted for k-bit number (doing n+2 to handle n=0 case): for i in range(int(log2(log2(n + 2))), -1, -1): n ^= n >> (1
@@syamkrishnareddypulagam6423 I have a list of concepts related to questions involving bitwise operations. Similarly for other topics as well. For example, concepts for bitwise questions include, testing for normal bitwise operations (XOR, AND, etc), masking, 1/2 complement, bit shifts, power of 2, base conversion, gray code, BCD, Hamming Code, XS3 Code, etc.
I remember struggling so much to solve this problem before but holy, didn't expect anyone to walk through this question so swiftly. Great as always, GOAT of Leetcode 👍
A lot of tech TH-camrs: "you don't need maths to be a software engineer" LeetCode: "lol" People who code and don't know/don't like maths after today's LeetCode question (searching TH-cam): "programming roles where they don't ask you math in technical interviews" Karma: "lol" Me writing this comment: thinking to myself how easy the question is literally just after seeing the solution.
Rather than call that formula "Binary tree", isn't it just a Geometric Progression with common ratio as 2? That's just a formula we learn in high school (Sum of a GP)
Ngl I feel like I need a therapy session after that problem ...
How long did it take you to figure it out from scratch the first time?
This is torture
Your explanation was super amazing. A couple of points:
- The list of binary numbers you generated represents the gray code.
- Sum of 2^k + 2^(k-1) + ... + 1 could be proved easily without the need to understand binary trees:
S = 2^k + 2^(k-1) + ... + 1 ..... multiply by 2 on both sides
2S = 2^(k+1) + 2^k + 2^(k-1) + ... + 2 .... add 1 and subtract 1 on the right side
2S = 2^(k+1) + [2^k + 2^(k-1) + ... + 2 + 1] - 1 .... the part in square brackets is S, what we started off with
2S = 2^(k+1) + S - 1.... rearrange
S = 2^(k+1) - 1
My solution: Time: O(log(b)) where b is the number of bits (e.g. 32 for int32), Space: O(1)
Note: time is not to be confused with O(log(n)), it is O(log(log(n))).
I tried to explain my intuition as clearly as I could. Please, bear with me. Thanks.
Explanation and intuition of solution: I started off in the same way as you did, wrote out the binary numbers (converting n to 0) and found out that they were the gray codes. So, the minimum number of operations is equal to how we arrived at that gray code, which is basically just converting the gray code to its binary representation.
E.g. if n=11, binary = 1011, we assume that this is the gray code (1011), and how did we arrive at this gray code is the binary number for this gray code = 1101 (13 in decimal).
Q. Why did we assume 1011 as gray code?
A. Because, if we trace back, converting this gray code to 0, this will give us the min operations (this is the property of gray code, that the adjacent codes differ by 1 bit).
Q. Why will converting gray code to binary (or decimal) will give us the result?
A. Because, initially, we assumed that given n is a gray code and not a binary, we want to reconstruct the original binary representation of n.
Summary: The problem simplifies just to converting gray code to binary number.
Enough with the talk. The code:
num ^= num >> 16
num ^= num >> 8
num ^= num >> 4
num ^= num >> 2
num ^= num >> 1
return num
The above solution is for 32-bit gray code to binary conversion.
Following solution is adapted for k-bit number (doing n+2 to handle n=0 case):
for i in range(int(log2(log2(n + 2))), -1, -1):
n ^= n >> (1
how the idea of gray code even flash to you. you are genius brother🙌
@@syamkrishnareddypulagam6423 I have a list of concepts related to questions involving bitwise operations. Similarly for other topics as well.
For example, concepts for bitwise questions include, testing for normal bitwise operations (XOR, AND, etc), masking, 1/2 complement, bit shifts, power of 2, base conversion, gray code, BCD, Hamming Code, XS3 Code, etc.
I remember struggling so much to solve this problem before but holy, didn't expect anyone to walk through this question so swiftly. Great as always, GOAT of Leetcode 👍
Neetcode saying "This is definitely a hard problem" means we should better avoid it
Saw you posting this video when I was struggling to understand the question in daily. Such a saviour!!
This is an extremely hard problem... But well explained, thank you very much !
Thanks for the explanation. Cheers.
keep going man lots of support from india!
The thing I hate about mathematical problems is that you can only solve them if you know a very particular algorithm.
Great explanation as always. Thank you. Also , thank you for the daily.
Woah! this explanation is amazing!
From 1:52 to 6:06 key concept which the problem description failed to do. Thanks you.
great explanation 👏
Great explanation!!
Thanks for the November badge
Thanks!
A lot of tech TH-camrs: "you don't need maths to be a software engineer"
LeetCode: "lol"
People who code and don't know/don't like maths after today's LeetCode question (searching TH-cam): "programming roles where they don't ask you math in technical interviews"
Karma: "lol"
Me writing this comment: thinking to myself how easy the question is literally just after seeing the solution.
Thanks for the daily
nice one bro
Is it more efficient to do it this way than to use the floor of log base two of n?
And someone is supposed to figure all this out and write the code for it within 45 minutes? 😢
It's crazy
No way I could’ve understood this problem from anywhere for sure
Rather than call that formula "Binary tree", isn't it just a Geometric Progression with common ratio as 2? That's just a formula we learn in high school (Sum of a GP)
geometric progression