Given an array A consisting of N constructive integers, the duty is to calculate the most XOR of the subarray of measurement Okay consisting of all distinct integers. If such subarray is just not current then Print “-1”.
Examples:
Enter: N = 10, A[] = [2, 3, 4, 2, 4, 5, 7, 4, 3, 9], Okay = 4
Output: 9
Rationalization : All Subarrays of measurement Okay 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 Most XOR of subarray is 9.Enter: N = 5, A[] = [2, 3, 2, 3, 2], Okay = 3
Output: -1
Rationalization: Since there of no subarray of measurement Okay with all integers distinct
Naive Answer: The essential option to clear up the issue is as follows:
A Easy Answer is to generate all subarrays of measurement Okay, test if all of the integers in that subarray are distinct, compute their XORs, and eventually return the utmost of all XORs, if no subarray of measurement Okay with all distinct is discovered return -1.
Under is the implementation of the above strategy:
C++
// C++ code for the above strategy:
#embody <bits/stdc++.h>
utilizing namespace std;
// Perform performing Calculation
int maximumXorsubarray(int N, vector<int>& A, int Okay)
{
// Variable for storing most XOR
// of the subarray of measurement Okay
int mx = -1;
// Producing all subarray of measurement Okay
for (int i = 0; i < N - Okay + 1; i++) {
// Set is used for storing the
// factor of subarray and
// checking distinct situation
unordered_set<int> st;
for (int j = i; j < i + Okay; j++) {
st.insert(A[j]);
}
// If subarray is of measurement Okay with
// all distinct
if (st.measurement() == Okay) {
// Calculating xor of the
// subarray of measurement Okay
int xorr = 0;
for (auto it : st) {
xorr = (xorr ^ it);
}
// replace mx
mx = max(mx, xorr);
}
}
// Returning the Most XOR of subarray
// of measurement Okay with all distict
return mx;
}
// Driver operate
int fundamental()
{
// Dimension of given subarray
int N = 10;
// Given array A
vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 };
// Dimension of subarray wanted
int Okay = 4;
// Perform Name
cout << "Most XOR of subarray of measurement Okay with all "
"distincts are : "
<< maximumXorsubarray(N, A, Okay);
return 0;
}
Most XOR of subarray of measurement Okay with all distincts are : 9
Time Complexity: O(N*Okay)
Auxiliary House: O(Okay)
Environment friendly Method: To unravel the issue observe the beneath thought:
On this strategy, we’ll use the XOR property that ( X XOR X ) is 0 and we’ve got to take a map that can retailer the frequencies of the integers and use the 2-pointer strategy, at any time when we get the factor whose frequency exceeds 1 or at any time when the scale the map will exceed Okay then we’ll shrink window in any other case we’ll broaden the window.
Under is the implementation of the above strategy:
C++
// C++ code for the above strategy:
#embody <bits/stdc++.h>
utilizing namespace std;
// Perform performing Calculation
int maximumXorsubarray(int N, vector<int>& A, int Okay)
{
// Variable for storing most XOR
// of the subarray of measurement Okay
int mx = -1;
// Declaring map which is used for
// storing frequencies
map<int, int> mp;
// Non permanent variable
int xorr = 0;
// Utilizing 2-pointers i, j
int i = 0;
for (int j = 0; j < N; j++) {
// Increasing the window
mp[A[j]]++;
xorr = (xorr xor A[j]);
// Shrinking the window
whereas (mp[A[j]] > 1 || mp.measurement() > Okay) {
mp[A[i]]--;
xorr = (xorr xor A[i]);
if (mp[A[i]] == 0)
mp.erase(A[i]);
i++;
}
// If measurement of window is the same as Okay
// then updating the mx variable
if ((j - i + 1) == Okay) {
mx = max(mx, xorr);
}
}
// Returning the Most XOR of subarray
// of measurement Okay with all distict
return mx;
}
// Driver operate
int fundamental()
{
// Dimension of given subarray
int N = 10;
// Given array A
vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 };
// Dimension of subarray wanted
int Okay = 4;
// Perform Name
cout << "Most XOR of subarray of measurement Okay with all "
"distict are : "
<< maximumXorsubarray(N, A, Okay);
return 0;
}
Most XOR of subarray of measurement Okay with all distict are : 9
Time Complexity: O(N*Log(Okay))
Auxiliary House: O(Okay)
