Neighboring Bitwise XOR - Leetcode 2683 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
10:34 - Coding Explanation

leetcode 2683

#neetcode #leetcode #python

[md_pedia]

great solution! Another approach, for anyone interested will be to calculate the total xor of the array. Since the problem states that the derived array is made from sm sorta cycle( last idx : n-1 ^ 0) it simply means that we will have 2 occurrences of each value in the derived array, which means that their xor need to be 0. :)

[gabrielignat]

wth
Your videos had multiple languages available? So cool

[tejas]

We are kinda having xor prblms from last 2 days 😂 and u know just cuz of u I solved them both without looking up at solution. Let's see if I can do this one also or not 😜

[jayshimsantaclara]

Your solution is easy to code out. With your videos bit manipulation is becoming fun for me. :)

[devkumar]

Simplest intuition I got is that a^a = 0
We are given for of all cyclic pairs
[a^b, b^c, c^a] here we need to find whether [a, b, c] exists or not
Just do this (a^b)^(b^c)^(c^a) == 0
Simple

[sivatejaysn]

loving brain teaser problems. solved on my own in first attempt

[Ahmad-hzv]

watched the first 2 mins and was able to code it by myself definetly going to draw things out like you do and try find patterns next time thank you!

[luizIIIIIIIIIIII]

thank you for your video

this was my solution:

class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
derivedXOR = 0
for bit in derived:
derivedXOR ^= bit
return derivedXOR == 0

the intuition is that the derived array is XORing every item in the original array twice. hence the result of the derived array XOR should be 0 as x ^ x = 0

[KhudoyshukurJuraev]

Let's define original as O
And derived as D

For the possible solution:
D[0] = O[0] ^ O[1]
D[1] = O[1] ^ O[2]
...
D[n-1] = O[n - 1] ^ O[n]
D[n] = O[n] ^ O[0]

if we regard this as system, and XOR both sides:

D[0] ^ D[1] ^ ... D[n-1 ^ D[n] = O[0] ^ O[1] ^ O[1] ^ O[2] .. O[n-1] ^ O[n] ^ O[n] ^ O[0]

If you look at the right side, every O[i] is participating twice. If that values are valid, their result should be 0.
That's why, you can just calculate all the XORs of derived and if the result is equal to 0, there is a possibility of making the original string.

[business_central]

Curious what you all think of my Solution:

class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
res = 0
for n in derived:
res ^= n

return res == 0


The logic is that the derived array must have an XOR sum that is 0 for us to be able to get the original array.
Example
0 1 0
this assumes that elements in first and last are same, and in the middle we have a different element - it's just not possible and the XOR sum won't be 0.

Hope it's clear, and helpful.

[rimputapa]

what you can also do instead of negating last is to XOR it with 1, although its a bit slower

[IharKatkavets-jw]

derived = [n1^n2, n2^n3, ..., n(k-1)^nk, nk^n1]
so if we XOR all elements in derived we have to get 0
for derived.count == 3, we have
n1^n2^n2^n3^n3^n1=0

[Tejesh-tt]

A more intuitive and simpler solution would be:
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
ans=0
for num in derived:
ans^=num
return ans==0
I think it's pretty self explanatory

[albin_joby]

since we are checking if the first and last values are same, which can only happend if there are even ones (zero has no influence ) .We could just use this one liner : return derived.count(1) % 2 == 0

[MacintoshPlusMB]

Ok, if the example is 1 1 0 1 1, then wouldn’t the derived array have different numbers for first and last but still be valid?

[MP-nyep]

Instead of returning first == last, we could also return last == 0. Since first is initialized to 0 and we never change it

[yurisich]

I run-spammed code to print all originals and their derived solutions up to 2**8, and noticed all of them had an even valued hamming weight. I took a look at missing values and they all had an odd hamming weight.

I wonder what would happen if I used my Leetcode execution context as a scientific calculator during an interview. That's how I do it on the job, but would it overcome the "can't reason through it" penalty? If I interviewed someone I'd let them run an interactive shell while getting to a solution.

[phaneeshachilaveni]

Python 1 line solution:
def doesValidArrayExist(derived):
return sum(derived)%2==0

[KISHORER-cz]

The easiest answer is XOR the whole derived array
This problem is like the yesterday's one....in the description of this problem you can notice that to form a derived array the elements in the original array repeat twice..when you XOR the same number then will become zero...BOOM answer reveled

[yash___]

Another approach is return sum(derived)%2 == 0 . Think about it why it works.