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. :)
@@yusufnzm i made it this way class Solution: def doesValidArrayExist(self, derived: List[int]) -> bool: res = 0 for d in derived: res ^=d return res == 0
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
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 😜
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.
i noticed that the amount of ones determines the result in a way, for each case, (i.e the derived array starts with either 0/1 or ends with 0/1). ones = derived.count(1) if derived[0]==0 and derived[-1]==1: if ones%2==0: return True else: return False elif derived[0]==0 and derived[-1]==0: if ones%2==0: return True else: return False elif derived[0]==1 and derived[-1]==1: if ones%2==0: return True else: return False else: if ones%2==0: return True else: return False
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
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
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
I had xor throght the dervied aray and returned true if the value is even but not sure how does works and stuckup with populating approach with lot of if else!!
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
so i solved this way let derived der , orignial org: then der would look something like this: der[0] = org[0] ^ org[1], der[1] = org[1] ^ org[2],..., der[n-1] = org[n-1] ^ org[0] then we can say that if we do xor of all element of der then it will contain all elements of org twice i.e xor of all elements of der = (xor of all elements of org) XOR (xor of all elements of org) and xor of 2 equal value is 0. Hence for a derived der there could be a org iff xor of all elements of der is 0. code: class Solution { public: bool doesValidArrayExist(vector& derived){ int derivedXor = 0; for(int b: derived) derivedXor ^= b; return !derivedXor; } }; I think if derived was a array of integers then this would also be true.
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
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. :)
IMHO, this is the intended solution and no need to simulate the original array
That is literally the hint 2 mentioned in leetcode.
Can you write the code for this approach please?
@@yusufnzm
i made it this way
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
res = 0
for d in derived:
res ^=d
return res == 0
@@hussamalqaza181 thats exactly the code i came up too except for some alterations in the return statement. Nonetheless the logic is the same
1:20 Frog
😂🐸
wth
Your videos had multiple languages available? So cool
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
Nice approach, but I can't understand, how does that prove the existence of [a,b,c]? Like (a^b)^(b^c)^(c^a) == 0 isn't this always true?
@yusufnzm it is given in q itself
nums[] = [x,y,z]
And binaryArray[] = [a,b,c]
Then x=a^b , y=b^c, z=c^a
This is already given in q , read carefully
@yusufnzm and (a^b)^(b^c)^(c^a) = ?
It will be 0 , if it's not 0 then [a,b,c] is not possible i.e. ans is false
nice bro, I just read this and solved the problem
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 😜
Your solution is easy to code out. With your videos bit manipulation is becoming fun for me. :)
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.
i solved the same way 😁👍
loving brain teaser problems. solved on my own in first attempt
i noticed that the amount of ones determines the result in a way, for each case, (i.e the derived array starts with either 0/1 or ends with 0/1).
ones = derived.count(1)
if derived[0]==0 and derived[-1]==1:
if ones%2==0:
return True
else:
return False
elif derived[0]==0 and derived[-1]==0:
if ones%2==0:
return True
else:
return False
elif derived[0]==1 and derived[-1]==1:
if ones%2==0:
return True
else:
return False
else:
if ones%2==0:
return True
else:
return False
Ouch, why do you have identical code through out all if blocks :/ you can factor it out to only
def f(derived):
return derived.count(1) % 2 == 0
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
return reduce(lambda x, y: x ^ y, derived) == 0
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!
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
nyc explanation
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
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?
Instead of returning first == last , we could also return last == 0. Since first is initialized to 0 and we never change it
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
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
I had xor throght the dervied aray and returned true if the value is even but not sure how does works
and stuckup with populating approach with lot of if else!!
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
so i solved this way let derived der , orignial org: then der would look something like this: der[0] = org[0] ^ org[1], der[1] = org[1] ^ org[2],..., der[n-1] = org[n-1] ^ org[0] then we can say that if we do xor of all element of der then it will contain all elements of org twice i.e xor of all elements of der = (xor of all elements of org) XOR (xor of all elements of org) and xor of 2 equal value is 0. Hence for a derived der there could be a org iff xor of all elements of der is 0.
code:
class Solution {
public:
bool doesValidArrayExist(vector& derived){
int derivedXor = 0;
for(int b: derived)
derivedXor ^= b;
return !derivedXor;
}
};
I think if derived was a array of integers then this would also be true.
@neetcodeio please make video on 1177. can make palindrome from substring
Python 1 line solution:
def doesValidArrayExist(derived):
return sum(derived)%2==0
I wrote a 12 line code to solve this and runtime was terrible...so well I took pen paper out this was all I came with
return sum(derived) % 2 != 0
Solution: Understand Hint 2...
Brother, why you are so consistent?😭😭
difficult to understand.
Used backtracking with n^2 567 passed 😂
Did you generate all possible permutations of 1's and 0's and XOR them?
Yeah
Good Morning Sir 🌞