Last Updated: 18 Aug, 2022

Game of XOR

Hard

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]

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

Solve now

Approaches

01 Approach

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):

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’.
Sort ‘ARR’ in ascending order.
Return the first and last elements in the order in an array.

Solve now

02 Approach

In the problem, if we observe the constraints of ‘X’ and ‘ARR’ the value can be utmost 1000. So after the XOR operation, the max value can be 1023. As for 9 bits number max value after XOR we can achieve is 1023.

So now we know that every element can not exceed 1023 after the operation.

We will maintain the count of numbers that are in the array. For a number ‘Y’ which is in the array 1 or more than 1 time denoted by ‘cnt[Y]’.

We will replace a few of these numbers ‘Y’ with ‘Y’⊕‘X’ and the remaining stay the same.

Consider the number ‘Y’ if there are ‘Z’ numbers smaller than ‘Y’ in the array then the number of ‘Y’ changes to ‘Y’⊕‘X’ can be found out by the ‘Z’.

If ‘Z’ is even then ceil(cnt[y]/2) will change to ‘Y’⊕‘X’ and remain stays same.

Else floor(cnt[y]/2) will change to ‘Y’⊕‘X’ and remain stays same.

We will iterate through all ‘K’ operations with maintaining the frequency of elements in ‘cnt’ array and create another array ‘currCnt’ in each operation and store the count of numbers after the execution of the operation. After each operation, we will replace ‘cnt’ with ‘currCnt’.

The steps are as follows:-

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

Create an array ‘cnt’ to store the count of the elements of the array of size 1024 with all values 0.
For each element ‘i’ in the array:
1. Increase ‘cnt[i]’ by 1.
For each operation in the range [0, ‘K’-1]:
1. Create another array ‘currCnt’ of size 1024 with all values 0.
2. Declare a flag ‘f’ with the value 0 which is used to check the number of elements before the current one is odd or even where 0 represents even and 1 represents odd.
3. For ‘i’ in range [0, 1023]:
  1. Increase ‘currCnt[i ^ X] by (cnt[i]+1-f)/2.
  2. Increase ‘currCnt[i] by (cnt[i]+f)/2.
4. Replace ‘cnt’ with ‘currCnt’.
Declare ‘minNum’ with 1024 and ‘maxNum’ with 0.
For i in range [0,1023]:
1. If cnt[i]>0:
  1. Replace ‘minNum’ with min(‘i’, ‘minNum’).
  2. Replace ‘maxNum’ with max(‘i’, ‘maxNum’).
Return an array with values {‘minNum’, ‘maxNum’}.

Solve now