PROBLEM LINK:
Practice
Contest
Author: conan_0
Tester: shivansh7
Editorialist: conan_0
DIFFICULTY: Easy
PRE-REQUISITES: Bit-manipulation
PROBLEM:
Let S={a_1,a_2....a_N} be some permutation of numbers from 1 to N .You are given Bitwise-XOR of consecutive elements of S i.e X= (a_1 \oplus a_2) ,(a_2 \oplus a_3),.....(a_{N-1} \oplus a_N) .
Now you have to find original elements a_1,a_2...a_N using above series.
Note- N is given odd.
EXPLANATION:
Let’s denote XOR of series S by P= a_1 \oplus a_2 \oplus a_3\oplus....a_{N-1}\oplus a_N, since
S is permutation of numbers from 1 to N, P=1\oplus 2\oplus 3\oplus....\oplus N. So value of P can be calculated in linear time.
Let’s take XOR of odd elements of series X i.e. (a_1 \oplus a_2), (a_3 \oplus a_4),....(a_{N-2} \oplus a_{N-1}) if we xor this series its value will be a_1 \oplus a_2 \oplus....a_{N
-1} (It will be missing last element of series P i.e. a_N).
Using these two series we can calculate value of a_N by XOR of these two series.
HOW?
P= a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1}\oplus a_N
R=a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1}
P \oplus R=(a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1}\oplus a_N) \oplus (a_1 \oplus a_2 \oplus a_3 \oplus.....\oplus a_{N-1})
Using commutative property of XOR
P \oplus R=(a_1 \oplus a_1) \oplus (a_2\oplus a_2)\oplus.....\oplus(a_{N-1} \oplus a_{N-1}) \oplus a_N
Since, a\oplus a=0
P \oplus R= 0 \oplus 0 \oplus...0 \oplus a _N
Also, a \oplus 0=a
P \oplus R=a_N
From value of a_N we can find the value a_{N-1} from last element X i.e. a_{N-1} \oplus a_N. Similarly by reverse iteration on X we can find values of a_{N-1}, a_{N-2}, a_{N-3}....a_3, a_2, a_1 in the given order. Thus original permutation is restored.
TIME COMPLEXITY: O(N)
SOLUTION: