Instead of using bit manipulation we can store x,y at the same place using nums[i]*1001+nums[i+n]. Because all the numbers are less than or equal to 1000.Then we will start traversing from end .Will get y part using nums[i]%1001 and x part using nums[i]/1001.
It feels a bit cheaty to use 32bit ints while 16bit would've been enough, that's basically hiding an output array in plain sight from the start. It's even possible to do in place permutations without the assumption that half of the bits are unused; by following the cycles: for t in 0 to 2n: s = source(t) while s < t: s = source(s) swap(s,t) def source(t): if t even then t/2 else t/2+n
Brilliant walkthrough of today's Leetcode challenge. As always. Question: Why not use `reversed(range(n))` in the for loop instead of (n-1, -1, -1)? Works the same, doesn't it?
Another simple 3 line python code to solve it in O(1) space: for i in range(n): nums[ 2 * i + 1 : 2 * i + 1 ]=[nums.pop( n + i )] return nums Here, nums[i:i] inserts any iterable (e.g. [2]) at ith index by shifting the rest of the elements right. However bit operations are computationally much more efficient, whereas here we have to shift elements to insert other elements.
Why do you not advertise this channel on your main? I feel like these videos would get more views if I had known that it existed other than getting them randomly recommended to me.
We are doing AND operation here to extract back the value of Y from the XY pair. Now, we know that in bits, we represent 2^0 as 1, 2^1 as 10, 2^2 as 100, and so on. Now, we want ten 1's so that we can AND it with the Y in XY(Y is the last ten digits in XY). For getting ten 1's we would do 2^10, but this would give 10000000000 (total 11 digits, one 1 and ten 0s), but we want ten 1's i.e. 1111111111, and hence we do 2^10-1 i.e. 2**10-1.
i think creating a array and returning the array won't cause any space complexity because i/p and o/p space are counted right? then first solution is also o(1) .............SC correct if I am wrong
H 'm sorry if this sounds silly, but when you say 32 bit, does it mean nums[0] is 32 bit , nums [ 1] is 32 bit and so on? also I didn't really understand the 10 bits part, like how is one array value 10 bits? Can someone please explain. I feel like I'm either unable to apply the basic concepts here or missing some basic information
Simple solution: res = [] for i in range(n): curr_first_half = nums[i] curr_2nd_half = nums[n + i] res.append(curr_first_half) res.append(curr_2nd_half) return res
Is this constant space? : def shuffle(self, nums: List[int], n: int) -> List[int]: for i in range(n): nums[i] = (nums[i],nums[i+n]) for i in range(n-1,-1,-1): nums[2*i],nums[(2*i)+1] = nums[i][0],nums[i][1] return nums
Oh wait, nvm. The introduction of tuples here means that our program allocates more space for those tuples as the size of our input grows (since we'll have n tuples). So the memory complexity is linear. I see exactly why we used the bitwise approach now.
the actual problem is easy
but implementing it ate my brain
That was a really smart solution. Never would have thought in this way.
Really smart solution. These daily problems are helping a lot. Thank you
Yes! I totally agree.
Instead of using bit manipulation we can store x,y at the same place using nums[i]*1001+nums[i+n]. Because all the numbers are less than or equal to 1000.Then we will start traversing from end .Will get y part using nums[i]%1001 and x part using nums[i]/1001.
bit operations as faster then arithmetic operations ☮
Ya but easier to remember for some.
This should be a medium-level problem lol. Definitely not easy (at least for me) to solve this in O(1) space complexity.
Agree very much !
It feels a bit cheaty to use 32bit ints while 16bit would've been enough, that's basically hiding an output array in plain sight from the start.
It's even possible to do in place permutations without the assumption that half of the bits are unused; by following the cycles:
for t in 0 to 2n:
s = source(t)
while s < t: s = source(s)
swap(s,t)
def source(t): if t even then t/2 else t/2+n
Brilliant walkthrough of today's Leetcode challenge. As always.
Question: Why not use `reversed(range(n))` in the for loop instead of (n-1, -1, -1)?
Works the same, doesn't it?
Yeah, that's definitely a cleaner way of writing it, will probably do it that way in the future!
nt
excellent idea. please keep up daily viedos!
Another simple 3 line python code to solve it in O(1) space:
for i in range(n):
nums[ 2 * i + 1 : 2 * i + 1 ]=[nums.pop( n + i )]
return nums
Here, nums[i:i] inserts any iterable (e.g. [2]) at ith index by shifting the rest of the elements right.
However bit operations are computationally much more efficient, whereas here we have to shift elements to insert other elements.
Best
Awesome content as usual
Why do you not advertise this channel on your main? I feel like these videos would get more views if I had known that it existed other than getting them randomly recommended to me.
True I agree too
this is mind opening 👌🏻✨👏🏻 thank you
Excellent explanation!
fantastic, at this poit it is more art then code
interviewers which expect people to solve this in o(1) space are just testing your memory / luck
Did not get the part
y = nums[ i ] & (2**10 -1)
I do know that we have to move y back to the end of the list but how is that helping here?
We are doing AND operation here to extract back the value of Y from the XY pair. Now, we know that in bits, we represent 2^0 as 1, 2^1 as 10, 2^2 as 100, and so on. Now, we want ten 1's so that we can AND it with the Y in XY(Y is the last ten digits in XY). For getting ten 1's we would do 2^10, but this would give 10000000000 (total 11 digits, one 1 and ten 0s), but we want ten 1's i.e. 1111111111, and hence we do 2^10-1 i.e. 2**10-1.
we can have values
i think creating a array and returning the array won't cause any space complexity because i/p and o/p space are counted right? then first solution is also o(1) .............SC correct if I am wrong
H
'm sorry if this sounds silly, but when you say 32 bit, does it mean nums[0] is 32 bit , nums [ 1] is 32 bit and so on?
also I didn't really understand the 10 bits part, like how is one array value 10 bits?
Can someone please explain. I feel like I'm either unable to apply the basic concepts here or missing some basic information
yes each number is occupying 32 bits and 10 bit is the actual number that occupying 10 bits and other bits are just filled with zeroes
Simple solution:
res = []
for i in range(n):
curr_first_half = nums[i]
curr_2nd_half = nums[n + i]
res.append(curr_first_half)
res.append(curr_2nd_half)
return res
lol this take o(n) space complexity instead of constant
Is this constant space? :
def shuffle(self, nums: List[int], n: int) -> List[int]:
for i in range(n):
nums[i] = (nums[i],nums[i+n])
for i in range(n-1,-1,-1):
nums[2*i],nums[(2*i)+1] = nums[i][0],nums[i][1]
return nums
Oh wait, nvm. The introduction of tuples here means that our program allocates more space for those tuples as the size of our input grows (since we'll have n tuples). So the memory complexity is linear. I see exactly why we used the bitwise approach now.
Here's my revised solution : def shuffle(self, nums: List[int], n: int) -> List[int]:
for i in range(n):
nums[i] 10
y = nums[i] & ((2**10)-1)
nums[2*i],nums[(2*i)+1] = x,y
return nums
Awesome
you lost me at bit manipulation