Ninja And XOR

Easy
0/40
Average time to solve is 20m
5 upvotes
Asked in companies
AdobeSnapdeal Ltd.

Problem statement

Ninja has been given an array/list ‘ARR’ having ‘N’ positive integers. Ninja wants to reconstruct the ‘ARR’ such that the newly formed array contains the XOR of consecutive elements in the ‘ARR’.

For Example: For ‘ARR’ = [1, 2, 3, 4, 5] the reconstructed ‘ARR’ will be [3, 1, 7, 1, 5].

1. The element at index  0 in the new ‘ARR’ is 3 because ‘ARR[0]’ ^ ‘ARR[1]’ is 1 ^ 2 which is equal to 3.

2. The element at index  1 in the new ‘ARR’ is 1 because ‘ARR[1]’ ^ ‘ARR[2]’ is 2 ^ 3 which is equal to 1.

3. The element at index  2 in the new ‘ARR’ is 7 because ‘ARR[2]’ ^ ‘ARR[3]’ is 3 ^ 4 which is equal to 7.

4. The element at index  3 in the new ‘ARR’ is 1 because ‘ARR[3]’ ^ ‘ARR[4]’ is 4 ^ 5 which is equal to 1.

5. The element at index  4 in the new ‘ARR’ is 5 because there is no element in the right of ‘ARR[4]’ so it will remain as it is in the new ‘ARR’.

Note:

As Ninja is busy with some other task, so he asks you for help. Can you help Ninja to reconstruct the ‘ARR’?
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer 'N' denoting the number of elements in the 'ARR'.

The second line of each test case contains 'N' single space-separated integers, denoting the element in the 'ARR'.
Output Format: 
For each test case, print a single line containing 'N' space-separated integers denoting the elements of reconstructed ‘ARR’.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 10 ^ 4
1 <= ARR[i] <= 10 ^ 7

Where 'T' is the number of test cases, 'N' denotes the number of elements in the 'ARR’ and 'ARR[i]' denotes the element at the ‘i’th index, respectively.

Time Limit: 1 sec
Sample Input 1:
2
2 
5 2 
1 
3
Sample Output 1:
7 2
3
Explanation of Sample Input 1:
For the first test case:
1. The element at index 0 in the new ‘ARR’ is 7 because  ‘ARR[0]’ ^ ‘ARR[1]’ is 5 ^ 2 which is equal to 7.
2. The element at index 1 in the new ‘ARR’ is 2 because there is no element in the right of ‘ARR[1]’ so it will remain as it is in the new ‘ARR’.  

For the second test case:
1. The element at index 0 in the new ‘ARR’ is 3 because there is no element in the right of ‘ARR[0]’ so it will remain as it is in the new ‘ARR’.
Sample Input 2:
2
4
5 5 5 5
3
2 4 8
Sample Output 2:
0 0 0 5
6 12 8
Explanation of Sample Input 2:
For the first test case:
1. The element at index 0 in the new ‘ARR’ is 0 because ‘ARR[0]’ ^ ‘ARR[1]’ is 5 ^ 5 which is equal to 0.
2. The element at index 1 in the new ‘ARR’ is 0 because ‘ARR[1]’ ^ ‘ARR[2]’ is 5 ^ 5 which is equal to 0.
3. The element at index 2 in the new ‘ARR’ is 0 because ‘ARR[2]’ ^ ‘ARR[3]’ is 5 ^ 5 which is equal to 0.
4. The element at index 3 in the new ‘ARR’ is 5 because there is no element in the right of ‘ARR[3]’ so it will remain as it is in the new ‘ARR’.

For the second test case:
1. The element at index 0 in the new ‘ARR’ is 6 because ‘ARR[0]’ ^ ‘ARR[1]’ is 2 ^ 4 which is equal to 6.
2. The element at index 1 in the new ‘ARR’ is 12 because ‘ARR[1]’ ^ ‘ARR[2]’ is 4 ^ 8 which is equal to 12.
3. The element at index 2 in the new ‘ARR’ is 8 because there is no element in the right of ‘ARR[2]’ so it will remain as it is in the new ‘ARR’.
Hint

Try to use the brute force approach in this problem 

Approaches (1)
Brute Force

The idea behind this approach is to simply iterate the ‘ARR’ and do the XOR operation for each consecutive element.

 

Here is the complete Algorithm:

  • Iterate the ‘ARR’ for ‘N-1’ times and for each element at index ‘i’ do the following:
    • Do the XOR operation on ‘ARR[i]’ and ‘ARR[i+1]’ and update the result at ‘ARR[i]’ as ‘ARR[i]’ = ‘ARR[i]’ ^ ‘ARR[i+1]’.
  • Finally, return ‘ARR’
Time Complexity

O(N), where N is the number of elements in the ’ARR’.

 

As we are iterating exactly one time over an array/list of length ‘N’.

Space Complexity

O(1).

 

As we are not using any extra space so the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ninja And XOR
Full screen
Console