I got one problem in one interview on binary tree permutation To create all possible combinations of numbers adding the right side of tree, you have to swap the left and right child and create these combinations and store in a array
num //= 2 could be replaced with num /= 2 since it's always going to be applied to even numbers as per the problem's premise. You could even replace it with num >>=2 if you wanna be fancy.
There are time codes in the video. You can also stop at the first solution. For example, I want to see different solutions, and I’m thankful to Navdeep for that possibility
17:47
today's Quote :-
I know this part is very confusing when you think about it , so best thing to do just not to think about it 🙂
For the first solution, are we able to factor in the "out of bound conditions" in the while loop?
Collatz conjecture for the win haha. The odd operation might not be exact but the derivative still follows similarly
Is it still a conjecture?
nice observation
I like this question, pretty interesting
Thank you for the explanation... ❤
if you convert the string into a deque at the start the simulation solution will be o(n) too, but the memory will be o(n)
i dont really get why the first is n^2? you mentioned that string manipulation is o(n) but we are working with lists?
Thank you.. this is a nice approach
Pleasre Reply
why dont't we Just convert the binary to decimal then check for odd event and count the steps
it's has 500 length string
it works for python but not for other languages
I love leetcode
Stockholm syndrome 😂
I got one problem in one interview on binary tree permutation
To create all possible combinations of numbers adding the right side of tree, you have to swap the left and right child and create these combinations and store in a array
Do you have the LC link for it ?
Why not convert the binary to a number and do the simulation? Wouldn't that be simpler
I think you may run into overflow if the number is very very big
@@jayberry6557 Not in Python apparently
I tried the same. One of my test cases failed. I don't know why.
Used bigint and worked fine
@@sdemji can you please share the solution here
Can't we just convert the binary number to decimal and then run while loop? It will come as O(N) right?
We could but in this case binary rep could be of length 500 even I suppose. Can’t convert that to a single decimal.
We can do xor operation instead of finding the actual value in 2nd solution.
if (s[i] == "1") ^ carry:
steps += 2
carry = 1
else:
steps += 1
that's literally the exact same solution except a bit harder if you're not familiar with xor. so he's solution simpler.
I love leetcode
why do u stop before the first element?
Solved it!
What if in simulation solution we convert the binary string into an integer. Will it still be an O(n**2) times solution or will it become O(n) ?
500 digits (from constraints) cannot fit integer
This doesn't relate directly to the code, but isn't the output explanation sounds like a form of Collatz Conjecture?
Nice❤
Isn't it a O(n) solution?
class Solution:
def numSteps(self, s: str) -> int:
decimal = int(s, 2) # convert to decimal
steps = 0
while True:
if decimal == 1:
return steps
if decimal % 2 == 0:
decimal = decimal // 2
else:
decimal += 1
steps += 1
I suppose, you wouldn't be allowed to convert input string to an integer in a real interview. Because it dramatically simplifies the task.
@@user-yj2ju9up8o true but it's not mentioned on the problem
do u do this everyday? or are these old recordings
He does the daily questions everyday and then posts the solutions if he hasn’t posted one already.
Hey everyone, welcome back and let’s write some NeetCode today!
some more neetcode?
lol too easy
steps = 0
num = int(s, 2)
while num != 1:
if num % 2 == 0:
num //= 2
elif num % 2 == 1:
num += 1
steps += 1
return steps
/s
The same solution without bit manipulations )
Here you can in now time count += 1 and use if / else
num //= 2 could be replaced with num /= 2 since it's always going to be applied to even numbers as per the problem's premise.
You could even replace it with num >>=2 if you wanna be fancy.
Input has 500 length string. Will work for only for python but not for other languages
I know you should use the tools you have to the fullest but this solution misses the whole point of the exercise
your videos are getting big, please do not do that...
disagree, some people would like to explore different solutions and the intuition behind each
There are time codes in the video. You can also stop at the first solution. For example, I want to see different solutions, and I’m thankful to Navdeep for that possibility
the bigger the better