Minimum Number of One Bit Operations to Make Integers Zero - Leetcode 1611 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/minimum...
0:00 - Read the problem
0:30 - Drawing Explanation
14:45 - Walk through the Algorithm
16:01 - Time / Space Complexity
16:43 - Coding Solution
leetcode 1611
#neetcode #leetcode #python

[@NeetCodeIO]

Ngl I feel like I need a therapy session after that problem ...

[@Infinitely16]

How long did it take you to figure it out from scratch the first time?

[@il5083]

This is torture

[@michael._.]

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 👍

[@jonaskhanwald566]

Neetcode saying "This is definitely a hard problem" means we should better avoid it

[@arihantbedagkar7678]

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]

how the idea of gray code even flash to you. you are genius brother🙌

[@arihantbedagkar7678]

@@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.

[@sauravsingh4497]

The thing I hate about mathematical problems is that you can only solve them if you know a very particular algorithm.

[@laumatthew71]

This is an extremely hard problem... But well explained, thank you very much !

[@kurejidiamond]

Saw you posting this video when I was struggling to understand the question in daily. Such a saviour!!

[@MP-ny3ep]

Great explanation as always. Thank you. Also , thank you for the daily.

[@itspurelypassionate]

Woah! this explanation is amazing!

[@GuruPrasadShukla]

keep going man lots of support from india!

[@Cheng-K]

Great explanation!!

[@avoo1d]

great explanation 👏

[@dera_ng]

A lot of tech CZcamsrs: "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 CZcams): "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.

[@nuamaaniqbal6373]

Thanks!

[@user-vd1bs6jr9b]

nice one bro

[@uptwist2260]

Thanks for the daily

[@yang5843]

Thanks for the November badge

[@sachinpaul2111]

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)

[@ialgorithms]

From 1:52 to 6:06 key concept which the problem description failed to do. Thanks you.

[@Codisrocks]

Is it more efficient to do it this way than to use the floor of log base two of n?

[@YT.Nikolay]

It's crazy

[@sidreddy7030]

No way I could’ve understood this problem from anywhere for sure

[@Infinitely16]

And someone is supposed to figure all this out and write the code for it within 45 minutes? 😢

[@paper-studio]

geometric progression

[@user-sn4nb3ei8p]