I would recommend reading the problem first.↵
Now that you have read it.↵
When we calculate the XOR of adjacent elements array eventually boils down to size 1.↵
But we need to stop at array length '2' because then only elements being equal makes sense.(Given in the problem.)↵
↵
NOTE:↵
XOR of two elements which are equal is '0'.↵
XOR of an element with '0' is the element itself.↵
↵
Now suppose we are reducing the array by calculating XORs.↵
Case 1: when the two elements are equal : ↵
Example : a b c d e e↵
At certain point(Greater than 3) if two adjacent elements are equal, then we obtain '0' as XOR.(e XOR e = 0)↵
We have : a b c d 0↵
Now when we XOR : a b c d ↵
↵
So we transformed array from a b c d e e -> a b c d ↵
↵
↵
Case 2 : when they are not equal : ↵
a b c d e f -> a b c d g (g= e XOR f)↵
↵
In both the cases we reduced the array size by 1 or 2.↵
↵
Suppose we reduce the array size to 4.↵
If its case 1 then we get an array of size 2. We stop here.↵
If its case 2 then we get an array of size 3. Now if its case 1 we would get 1 element, which is not feasible. Otherwise if its case 2 we would get 2 elements.↵
↵
↵
At the end we are left with 2 or 3 set of elements, which are obtained from XORing adjacent elements.↵
So we could find 2 partitions of array, XORing these two partitions we get '0' then its a YES.↵
Or we could find three partitions of array, XORing these three parts we get '0', then its a YES else NO.↵
↵
Case 1: TWO PARTS — ↵
If we are left with 2 elements, then both the elements(element1 and element2) should be equal. If they are equal then element1 XOR element2 is 0.↵
Element1 was obtained from some adjacent elements XOR.↵
Element2 was obtained from some adjacent elements XOR.↵
Therefore, if Element1 XOR Element2 is zero. The XOR of whole array must have been 0 to get this.↵
↵
↵
Case 2 : THREE PARTS:↵
↵
You could use two nested loops for two pointers which would split the array into three parts.↵
↵
Use prefix array to calculate XORs from 1 to i- index and store it.↵
↵
a b c d e f g ↵
↵
XOR of{c,d} = XOR of(a,b,c,d) XOR XOR of(a,b).↵
Why so?↵
a^b^c^d^a^b = c^d [As x^x = 0 && 0 ^ x = x]↵
↵
↵
Using this calculate the XOR of three parts of every possible partition. If you find the XOR of these parts equal for a partition print YES else NO.
Now that you have read it.↵
When we calculate the XOR of adjacent elements array eventually boils down to size 1.↵
But we need to stop at array length '2' because then only elements being equal makes sense.(Given in the problem.)↵
↵
NOTE:↵
XOR of two elements which are equal is '0'.↵
XOR of an element with '0' is the element itself.↵
↵
Now suppose we are reducing the array by calculating XORs.↵
Case 1: when the two elements are equal : ↵
Example : a b c d e e↵
At certain point(Greater than 3) if two adjacent elements are equal, then we obtain '0' as XOR.(e XOR e = 0)↵
We have : a b c d 0↵
Now when we XOR : a b c d ↵
↵
So we transformed array from a b c d e e -> a b c d ↵
↵
↵
Case 2 : when they are not equal : ↵
a b c d e f -> a b c d g (g= e XOR f)↵
↵
In both the cases we reduced the array size by 1 or 2.↵
↵
Suppose we reduce the array size to 4.↵
If its case 1 then we get an array of size 2. We stop here.↵
If its case 2 then we get an array of size 3. Now if its case 1 we would get 1 element, which is not feasible. Otherwise if its case 2 we would get 2 elements.↵
↵
↵
At the end we are left with 2 or 3 set of elements, which are obtained from XORing adjacent elements.↵
So we could find 2 partitions of array, XORing these two partitions we get '0' then its a YES.↵
Or we could find three partitions of array, XORing these three parts we get '0', then its a YES else NO.↵
↵
Case 1: TWO PARTS — ↵
If we are left with 2 elements, then both the elements(element1 and element2) should be equal. If they are equal then element1 XOR element2 is 0.↵
Element1 was obtained from some adjacent elements XOR.↵
Element2 was obtained from some adjacent elements XOR.↵
Therefore, if Element1 XOR Element2 is zero. The XOR of whole array must have been 0 to get this.↵
↵
↵
Case 2 : THREE PARTS:↵
↵
You could use two nested loops for two pointers which would split the array into three parts.↵
↵
Use prefix array to calculate XORs from 1 to i- index and store it.↵
↵
a b c d e f g ↵
↵
XOR of{c,d} = XOR of(a,b,c,d) XOR XOR of(a,b).↵
Why so?↵
a^b^c^d^a^b = c^d [As x^x = 0 && 0 ^ x = x]↵
↵
↵
Using this calculate the XOR of three parts of every possible partition. If you find the XOR of these parts equal for a partition print YES else NO.
