Minimum Array End - Leetcode 3133 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
9:08 - Coding Explanation
10:50 - Drawing Explanation
19:27 - Coding Explanation

leetcode 3133

#neetcode #leetcode #python

[dhairyashah]

I tried to understand the second approach like 10 times but still don't understand fully. Anyone in the same boat?

[treelibrarian]

this is one of those rare occasions where something is easier in assembly ;)
x64-bmi2 has an instruction PDEP (parallel bits deposit) which makes it trivial. If pdep(from, to) is a function that uses pdep to deposit the bits of *from* at the positions indicated in *to*:

uint64_t MinArrEnd(uint64_t X, uint64_t N) { return X | pdep(N-1, ~X); }

is the entire solution.

In asm it's 6 instructions, including the RET to return from the function.

why? because the AND requires that all elements in the array must have all the set bits of X also set, only the unset bits of X can be used for counting. If we start counting at zero, N elements reaches N-1 count, so spread the bits of N-1 to the unset positions of X, then OR with X, and you have the minimum possible final element of the array.



the pdep instruction takes the bits of the "from" input and spreads them into the positions indicated by the set bits in the "to" mask, so for example:
mask: 101101000110111010
bits: 0111000111
result:

[Airoxen]

Came up with the optimal solution on my own without any hints. Such a good problem. If you just follow a coherent line of reasoning, and list out all your observations, you can figure it out.

[kapilvermani]

Not sure how one can come up with idea that to get next number with same bit characteristics as x we need to increment x by 1 and then OR. Simply impossible for ordinary souls like me😊

[ahmedahmedahmed-vo]

the first solution actually passed With golang :)

[betterworld]

clean:

class Solution:
def minEnd(self, n: int, x: int) -> int:
ans = x
i = 0
n -= 1
while n:
while (ans >> i) & 1 != 0:
i += 1
ans = ans | ((n & 1) << i)
n = n >> 1
i += 1
return ans

[AlfredPros]

The alternative and shorter solution to this would be to convert the number to list of bits. We iterate through x from the last bit to the first. Whenever, 0 bit is found, pop the target list and replace the x bit. Once all x list or target list has been traversed, the result is the target and x list combined.

def minEnd(self, n: int, x: int) -> int:
cur = list(bin(x)[2:])
target = list(bin(n-1)[2:])
ptr = len(cur)-1

while ptr and target:
if cur[ptr] == '0':
cur[ptr] = target.pop()
ptr -= 1

return int(''.join(target + cur), 2)

[meylyssa]

Such a good explanation! As always, neetcode == quality.

[andrerrh]

Really liked your approach and explanation on this one man, thank you for the amazing content!

[alexgusev]

At 15:08 there's a great explanation for not TLE solution

[yang]

First

This problem is interesting, I've been enjoying the bit manipulation problems lately

[Algo_Artisan]

First solution: 👨‍🔧 Functional, like a trusty old car.

Second solution: 🚀 Next-level! Fasten your seatbelt, it’s turbo-charged!

[JamesBond-mqpd]

no clue why adding x to n -1 with two pointers equal to answer

[luizfelipe]

I solved this problem using the first approach. But honestly, I couldn't make the second one. Even after watching this, I do not understand why this works.

[mcbotface]

i suck at bitwise math.
large = 2**64-1
changeables = list(bin(large^x)[-1:1:-1])
xbsl = list(bin(x)[-1:1:-1])
nm1 = list(bin(n-1)[2:])

for i, bit in enumerate(changeables):
if bit=="1":
if nm1:
xbsl[i] = nm1.pop()
else:
break
return int(''.join(xbsl)[::-1], 2)

[dusvn]

You should add facecam at every video it's nice to see you

[ShivsharanSanjawad]

long long minEnd(int n, int x) {
long long ans = x ;
long long temp = ans ;
long long y = n-1 ;
while(y>0){
long long bit = y&1 ;
long long mask = ~temp&(temp+1) ;
if(bit==1){
ans = ans|mask ;
}
temp = temp |mask ;
y = y>>1 ;
}
return ans;
}, , , , more efficient one but when you analyze on it mathemtically, basically in video he is checking the x's bit one by one whether it is one or zero and if zero then doing or, but i got the last unset bit and did or in one and setted it in another variable so that i next time i get next unset bit .

[shakkar]

Stopped 33 seconds into the video the whole problem is just pext
edit: apparently it was the reverse of pext, which is pdep, thing == pext(pdep(thing, mask), mask)

[TheSmashten]

Hate this question but thanks for the vid

[Axel.Blazer]

this one `bits` 100% runtimes lol

class Solution:
def minEnd(self, n: int, x: int) -> int:
x = deque(bin(x)[2:])
n_bin = bin(n - 1)[2:]
n_len = len(n_bin)

# Embed n-1 into the 0's of x
j = n_len - 1
for i in range(len(x) - 1, -1, -1):
if j < 0:
break
if x[i] == '0':
x[i] = n_bin[j]
j -= 1

# prepend remaining bits
while j >= 0:
x.appendleft(n_bin[j])
j -= 1

return int("".join(x), 2)
# 4 100
# 5 101
# 6 110