Maximum XOR subarray of K distinct integer

By Ann Roberts On Feb 3, 2023

Given an array A consisting of N positive integers, the task is to calculate the maximum XOR of the subarray of size K consisting of all distinct integers. If such subarray is not present then Print “-1”.

Examples:

Input: N = 10, A[] = [2, 3, 4, 2, 4, 5, 7, 4, 3, 9], K = 4
Output: 9
Explanation : All Subarrays of size K with all distinct integers are [2, 4, 5, 7], [5, 7, 4, 3], [7, 4, 3, 9] and there XOR are 6, 5, 9 respectively. So Maximum XOR of subarray is 9.

Input: N = 5, A[] = [2, 3, 2, 3, 2], K = 3
Output: -1
Explanation: Since there of no subarray of size K with all integers distinct

Naive Solution: The basic way to solve the problem is as follows:

A Simple Solution is to generate all subarrays of size K, check if all the integers in that subarray are distinct, compute their XORs, and finally return the maximum of all XORs, if no subarray of size K with all distinct is found return -1.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int maximumXorsubarray(int N, vector<int>& A, int K)

{

int mx = -1;

for (int i = 0; i < N - K + 1; i++) {

unordered_set<int> st;

for (int j = i; j < i + K; j++) {

st.insert(A[j]);

}

if (st.size() == K) {

int xorr = 0;

for (auto it : st) {

xorr = (xorr ^ it);

}

mx = max(mx, xorr);

}

return mx;

}

int main()

{

int N = 10;

vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 };

int K = 4;

cout << "Maximum XOR of subarray of size K with all "

"distincts are : "

<< maximumXorsubarray(N, A, K);

return 0;

}

Output

Maximum XOR of subarray of size K with all distincts are : 9

Time Complexity: O(N*K)
Auxiliary Space: O(K)

Efficient Approach: To solve the problem follow the below idea:

In this approach, we will use the XOR property that ( X XOR X ) is 0 and we have to take a map that will store the frequencies of the integers and use the 2-pointer approach, whenever we get the element whose frequency exceeds 1 or whenever the size the map will exceed K then we will shrink window otherwise we will expand the window.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int maximumXorsubarray(int N, vector<int>& A, int K)

{

int mx = -1;

map<int, int> mp;

int xorr = 0;

int i = 0;

for (int j = 0; j < N; j++) {

mp[A[j]]++;

xorr = (xorr xor A[j]);

while (mp[A[j]] > 1 || mp.size() > K) {

mp[A[i]]--;

xorr = (xorr xor A[i]);

if (mp[A[i]] == 0)

mp.erase(A[i]);

i++;

}

if ((j - i + 1) == K) {

mx = max(mx, xorr);

}

return mx;

}

int main()

{

int N = 10;

vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 };

int K = 4;

cout << "Maximum XOR of subarray of size K with all "

"distict are : "

<< maximumXorsubarray(N, A, K);

return 0;

}

Output

Maximum XOR of subarray of size K with all distict are : 9

Time Complexity: O(N*Log(K))
Auxiliary Space: O(K)

Examples:

Input: N = 10, A[] = [2, 3, 4, 2, 4, 5, 7, 4, 3, 9], K = 4
Output: 9
Explanation : All Subarrays of size K with all distinct integers are [2, 4, 5, 7], [5, 7, 4, 3], [7, 4, 3, 9] and there XOR are 6, 5, 9 respectively. So Maximum XOR of subarray is 9.

Input: N = 5, A[] = [2, 3, 2, 3, 2], K = 3
Output: -1
Explanation: Since there of no subarray of size K with all integers distinct

Naive Solution: The basic way to solve the problem is as follows:

A Simple Solution is to generate all subarrays of size K, check if all the integers in that subarray are distinct, compute their XORs, and finally return the maximum of all XORs, if no subarray of size K with all distinct is found return -1.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int maximumXorsubarray(int N, vector<int>& A, int K)

{

int mx = -1;

for (int i = 0; i < N - K + 1; i++) {

unordered_set<int> st;

for (int j = i; j < i + K; j++) {

st.insert(A[j]);

}

if (st.size() == K) {

int xorr = 0;

for (auto it : st) {

xorr = (xorr ^ it);

}

mx = max(mx, xorr);

}

return mx;

}

int main()

{

int N = 10;

vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 };

int K = 4;

cout << "Maximum XOR of subarray of size K with all "

"distincts are : "

<< maximumXorsubarray(N, A, K);

return 0;

}

Output

Maximum XOR of subarray of size K with all distincts are : 9

Time Complexity: O(N*K)
Auxiliary Space: O(K)

Efficient Approach: To solve the problem follow the below idea:

In this approach, we will use the XOR property that ( X XOR X ) is 0 and we have to take a map that will store the frequencies of the integers and use the 2-pointer approach, whenever we get the element whose frequency exceeds 1 or whenever the size the map will exceed K then we will shrink window otherwise we will expand the window.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int maximumXorsubarray(int N, vector<int>& A, int K)

{

int mx = -1;

map<int, int> mp;

int xorr = 0;

int i = 0;

for (int j = 0; j < N; j++) {

mp[A[j]]++;

xorr = (xorr xor A[j]);

while (mp[A[j]] > 1 || mp.size() > K) {

mp[A[i]]--;

xorr = (xorr xor A[i]);

if (mp[A[i]] == 0)

mp.erase(A[i]);

i++;

}

if ((j - i + 1) == K) {

mx = max(mx, xorr);

}

return mx;

}

int main()

{

int N = 10;

vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 };

int K = 4;

cout << "Maximum XOR of subarray of size K with all "

"distict are : "

<< maximumXorsubarray(N, A, K);

return 0;

}

Output

Maximum XOR of subarray of size K with all distict are : 9

Time Complexity: O(N*Log(K))
Auxiliary Space: O(K)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.