Minimum Array End - Leetcode 3133 - Python

[@takeuchi5760]

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.

[@dhairyashah4472]

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

[@mohamedasifar]

🙌🏻

[@cooldudeachyut]

Haven't watched the video but I tried to do it myself through O(1) approach first. Basically we need to preserve the 1s in binary representation of x in each number in the sequence, and come up with a number that's the largest combination under the restriction (i < n) while they must all be increasing. The reason being that bitwise AND operation only preserves 1s if every number in the sequence has 1 at that position. Lets say x = 14, n = 6. x(binary) = 0 0 1 1 1 0, we have to preserve the 1s positions (3rd, 4th and 5th) but can freely change the 0, and the leading zeros (I've only included 2 leading zeros here) upto 64 positions for a long type number. Now one thing to notice is if we are creating n combinations with such a restriction, x itself would be the first number in the sequence. As changing any "0" in x would only cause the number to increase. By this logic let's see all strictly increasing combinations in the sequence. The numbers should be as close as possible so the last number is the smallest possible answer that satisfies the condition. 0 0 [1 1 1] 0 0 0 [1 1 1] 1 0 1 [1 1 1] 0 0 1 [1 1 1] 1 1 0 [1 1 1] 0 1 0 [1 1 1] 1

[@ИгорьДубинин-у6ч]

@@cooldudeachyut Best explanation why we change zeros to n -1

[@dhairyashah4472]

@cooldudeachyut amazing explanation, buddy, thank you pattern for the whole numbers from 0 - n-1 and then adding directly to the x. This explanation was really amazing. I kind of knew that we were adding n-1 to x, but was having hard time understanding the combination part. This explanation cleared my doubts. ✌️

[@mohammedsuhail.s192]

me too

[@treelibrarian7618]

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: 001101000000011010

[@betterworld1917]

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) > 1 i += 1 return ans

[@elmalkiahmed-v7o]

the first solution actually passed With golang :)

[@kapilvermani2575]

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😊

[@segue97]

I think we increment by x by 1 because its guarantees to give us the smallest possible number which is were the greedy approach comes in.

[@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)

[@meylyssa3666]

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!

[@Algo_Artisan]

First solution: 👨‍🔧 Functional, like a trusty old car. Second solution: 🚀 Next-level! Fasten your seatbelt, it’s turbo-charged!

[@zoeycvu]

neetcode = breakfast + leetcode

[@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:]) xbsl.extend(['0']*(64-len(xbsl))) for i, bit in enumerate(changeables): if bit=="1": if nm1: xbsl[i] = nm1.pop() else: break return int(''.join(xbsl)[::-1], 2)

[@alexgusev8118]

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

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

[@luizfelipe2330]

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.

[@killuaa_89]

same here cant get my head around second approach.

[@user-wx8bm1pg1d]

I'm the opposite. I figured out an approach similar to the 2nd pretty quickly but it doesn't seem obvious to me why adding one then ORing would work

[@mahtab319]

@@user-wx8bm1pg1d yep same i did understood i need to ignore the 1s of x and fill in the remaining 0s with the max number. But i couldn't relate it to the n-1 part. That was really clever. And yeah i still have no idea why the 1st approach works lol.

[@yang5843]

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

[@dusvn1484]

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

[@asango_aham]

Gay

[@dusvn1484]

@ For me From primary school to uni is better to watch profesor when they explain somethijg.Idk why but I better understand then.

[@mgik-or-something]

@@asango_aham It's papa NeetCode. I would be gay for him.

[@JamesBond-mq7pd]

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

[@takeuchi5760]

Because for AND of all to be x. All of them must have the x bits as set. Now the bits other than that are used to make an increasing sequence, and to make an increasing sequence in binary, when you start writing out sequences you'll notice it's following the binary counting pattern. So just adding n-1 means getting n-1 numbers starting from x.

[@shakkar23]

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)

[@devmahad]

thanks :)

[@MacintoshPlus1MB]

Hello Neet Code

[@SKSB5502]

passed all in java

[@rudreshraj1298]

bro can you provide the java code for the second method

[@Akash.B28]

​@@rudreshraj1298 see leetcode editorial

[@antonyr6307]

@@rudreshraj1298 class Solution { public long minEnd(int n, int x) { long res = x; // Start with the first element being x long i_x = 1; // Mask long i_n = 1; // Counter while (i_n

[@onehmong9368]

Sorry no bitwise drals

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