When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

amireripmav786's blog

By amireripmav786, history, 3 years ago, In English

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.

  • Vote: I like it
  • -16
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

not gonna lie, this is completely different solution from the editorial solution xD

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it would be better if you highlight some important points you want to talk about... which are different that what is given in the editorial.