Game of XOR

Hard
0/120
profile
Contributed by
0 upvote

Problem statement

You are given an array ‘ARR’ of integers of size ‘N’ and an integer ‘X’. You have to perform the following operation exactly ‘K’ times.

First sort the array then replace every odd indexed element ‘ARR[i]’ with ‘ARR[i]’ ⊕ ‘X’ 
Where 1 <= ‘i’ <= ‘N’ and ⊕ is bitwise xor.

After completion of the operations tell the minimum and maximum number in the array ‘ARR’ respectively.

Note: In the Problem Statement 1-based indexing is used and in the code, 0-based indexing is used.

Example: 
Input: ‘N’ = 4  ‘K’ = 1  ‘X’ = 2 ‘ARR’ = [2, 3, 1 , 4]

Output: 1 
The execution of the operation is as follows :
[2, 3, 1, 4] =>Sort => [1, 2, 3, 4] => [1⊕2, 2, 3⊕2, 4] => [3, 2, 1, 4]
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’, denoting the number of test cases.    

The First line of each test case contains three integers ‘N’, ‘K’, ‘X’.

The Second line contains ‘N’ numbers representing elements of the ‘ARR’.
Output format : 
Return Minimum and Maximum in order of the array ‘ARR’ after performing ‘K’ operations.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100   
1 <= N <= 10^5
1 <= K <= 10^4
0 <= X, ARR[i] <= 1000

Time Limit: 1 sec
Sample Input 1 :
2
4 1 2
2 3 1 4
4 2 4  
5 3 2 8
Sample Output 1 :
1 2
2 8
Explanation Of Sample Input 1 :
For the first test case:-
The execution of the operation is as follows :
[2, 3, 1, 4] =>Sort => [1, 2, 3, 4] => [1⊕2, 2, 3⊕2, 4] => [3, 2, 1, 4]

For the second test case:-
The execution of the operations is as follows :
[5, 3, 2, 8] =>Sort => [2, 3, 5, 8] => [2⊕4, 3, 5⊕4, 8] => [6, 3, 1, 8]
[6, 3,1, 8] =>Sort => [1, 3, 6, 8] => [1⊕4, 3, 6⊕4, 8] => [5, 3, 2, 8]
Sample Input 2 :
2
5 3 3
32 31 50 5 1 
8 4 7
28 43 43 18 39 33 16 30
Sample Output 2 :
2 49
21 44
Hint

Perform All the operations as given.

Approaches (2)
Brute Force

For ‘K’ operations for each operation we first sort ‘ARR’ then we perform the second part of the operation of XORing all the odd indexed elements with ‘X’. 

After the above step, we again sort ‘ARR’ and return the first and last element of the ‘ARR’.

 

The steps are as follows:-

function xorGame(int N, int K, int X, [int] ARR):

  1. For i from [0, K-1]
    1. Sort the array ‘ARR’.
    2. For ‘j’ in the range [0, n-1] with each time ‘j’ increases by 2.
      • Replace ‘ARR[j]’ with ‘ARR[j]’ ⊕ ‘X’.
  2. Sort ‘ARR’ in ascending order.
  3. Return the first and last elements in the order in an array.
Time Complexity

O( K * N * log( N ) + N * log( N ) ), Where ‘N’ is the number of elements in ‘ARR’, ‘K’ is the number of times we have to perform the given operation. 

 

We are performing the operation ‘K’ time and in the operation, we sort the array which takes O( N * log( N ) ), and traversing takes O( N ) so we take the max of it.

After completion of the ‘K’ operation, we again sort the array.

Hence the time complexity is O( K * N * log( N ) + N * log( N ) ).

Space Complexity

O( 1 ).

 

We are not using any extra space.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Game of XOR
Full screen
Console