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

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

Рет қаралды 7,323

Күн бұрын

🚀 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

Пікірлер: 29

@NeetCodeIO 7 ай бұрын

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

@Infinitely16 7 ай бұрын

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

@il5083 7 ай бұрын

This is torture

@jonaskhanwald566 7 ай бұрын

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

@arihantbedagkar7678 7 ай бұрын

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 7 ай бұрын

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

@arihantbedagkar7678 7 ай бұрын

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

@michael._. 7 ай бұрын

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 👍

@sauravsingh4497 7 ай бұрын

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

@kurejidiamond 7 ай бұрын

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

@Infinitely16 7 ай бұрын

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

@laumatthew71 7 ай бұрын

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

@GuruPrasadShukla 7 ай бұрын

keep going man lots of support from india!

@MP-ny3ep 7 ай бұрын

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

@itspurelypassionate 7 ай бұрын

Woah! this explanation is amazing!

@Cheng-K 7 ай бұрын

Great explanation!!

@Codisrocks 7 ай бұрын

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

@avoo1d 7 ай бұрын

great explanation 👏

@dera_ng 7 ай бұрын

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

@user-vd1bs6jr9b 7 ай бұрын

nice one bro

@sachinpaul2111 7 ай бұрын

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)