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++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function performing Calculationint maximumXorsubarray(int N, vector<int>& A, int K){ // Variable for storing maximum XOR // of the subarray of size K int mx = -1; // Generating all subarray of size K for (int i = 0; i < N - K + 1; i++) { // Set is used for storing the // element of subarray and // checking distinct condition unordered_set<int> st; for (int j = i; j < i + K; j++) { st.insert(A[j]); } // If subarray is of size K with // all distinct if (st.size() == K) { // Calculating xor of the // subarray of size K int xorr = 0; for (auto it : st) { xorr = (xorr ^ it); } // update mx mx = max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct return mx;}// Driver functionint main(){ // Size of given subarray int N = 10; // Given array A vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 }; // Size of subarray needed int K = 4; // Function Call cout << "Maximum XOR of subarray of size K with all " "distincts are : " << maximumXorsubarray(N, A, K); return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG {// Function performing Calculationstatic int maximumXorsubarray(int N,int A[], int K){ // Variable for storing maximum XOR // of the subarray of size K int mx = -1; // Generating all subarray of size K for (int i = 0; i < N - K + 1; i++) { // Set is used for storing the // element of subarray and // checking distinct condition Set<Integer> st = new HashSet<>(); for (int j = i; j < i + K; j++) { st.add(A[j]); } // If subarray is of size K with // all distinct if (st.size() == K) { // Calculating xor of the // subarray of size K int xorr = 0; for (Integer it : st) { xorr = (xorr ^ it); } // update mx mx = Math.max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct return mx;}// Driver function public static void main (String[] args) { // Size of given subarray int N = 10; // Given array A int A[] = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 }; // Size of subarray needed int K = 4; // Function Call System.out.println( "Maximum XOR of subarray of size K with all distincts are : " + maximumXorsubarray(N, A, K)); }} |
Python3
# Python3 code for the above approachfrom typing import List# Function performing Calculationdef maximumXorsubarray(N: int, A: List[int], K: int) -> int: # Variable for storing maximum XOR # of the subarray of size K mx = -1 # Generating all subarray of size K for i in range(N - K + 1): # Set is used for storing the # element of subarray and # checking distinct condition st = set() for j in range(i, i + K): st.add(A[j]) # If subarray is of size K with # all distinct if len(st) == K: # Calculating xor of the # subarray of size K xorr = 0 for it in st: xorr = (xorr ^ it) # update mx mx = max(mx, xorr) # Returning the Maximum XOR of subarray # of size K with all distinct return mx# Driver functionif __name__ == "__main__": # Size of given subarray N = 10 # Given array A A = [2, 3, 4, 2, 4, 5, 7, 4, 3, 9] # Size of subarray needed K = 4 # Function Call print("Maximum XOR of subarray of size K with all distincts are : ", maximumXorsubarray(N, A, K))# This code is contributed by lokeshpotta20. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG { // Function performing Calculation static int MaximumXorSubarray(int N, int[] A, int K) { // Variable for storing maximum XOR of the subarray // of size K int mx = -1; // Generating all subarray of size K for (int i = 0; i < N - K + 1; i++) { // Set is used for storing the element of // subarray and checking distinct condition HashSet<int> st = new HashSet<int>(); for (int j = i; j < i + K; j++) { st.Add(A[j]); } // If subarray is of size K with all distinct if (st.Count == K) { // Calculating xor of the subarray of size K int xorr = 0; foreach(int it in st) { xorr = (xorr ^ it); } // update mx mx = Math.Max(mx, xorr); } } // Returning the Maximum XOR of subarray of size K // with all distinct return mx; } static public void Main() { // Code // Size of given subarray int N = 10; // Given array A int[] A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 }; // Size of subarray needed int K = 4; // Function Call Console.WriteLine( "Maximum XOR of subarray of size K with all distincts are : " + MaximumXorSubarray(N, A, K)); }}// This code is contributed by sankar. |
Javascript
// Function performing Calculationfunction maximumXorsubarray(N, A, K) { // Variable for storing maximum XOR // of the subarray of size K let mx = -1; // Generating all subarray of size K for (let i = 0; i <= N - K; i++) { // Set is used for storing the // element of subarray and // checking distinct condition let st = new Set(); for (let j = i; j < i + K; j++) { st.add(A[j]); } // If subarray is of size K with // all distinct if (st.size === K) { // Calculating xor of the // subarray of size K let xorr = 0; for (let it of st) { xorr = (xorr ^ it); } // update mx mx = Math.max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct return mx;}// Driver functionconst N = 10;const A = [2, 3, 4, 2, 4, 5, 7, 4, 3, 9];const K = 4;// Function Callconsole.log("Maximum XOR of subarray of size K with all distincts are : ", maximumXorsubarray(N, A, K)); |
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 of 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++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function performing Calculationint maximumXorsubarray(int N, vector<int>& A, int K){ // Variable for storing maximum XOR // of the subarray of size K int mx = -1; // Declaring map which is used for // storing frequencies map<int, int> mp; // Temporary variable int xorr = 0; // Using 2-pointers i, j int i = 0; for (int j = 0; j < N; j++) { // Expanding the window mp[A[j]]++; xorr = (xorr xor A[j]); // Shrinking the window 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 size of window is equal to K // then updating the mx variable if ((j - i + 1) == K) { mx = max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct return mx;}// Driver functionint main(){ // Size of given subarray int N = 10; // Given array A vector<int> A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 }; // Size of subarray needed int K = 4; // Function Call cout << "Maximum XOR of subarray of size K with all " "distinct are : " << maximumXorsubarray(N, A, K); return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { // Function performing Calculation static int maximumXorsubarray(int N, int[] A, int K) { // Variable for storing maximum XOR // of the subarray of size K int mx = -1; // Declaring map which is used for // storing frequencies Map<Integer, Integer> mp = new HashMap<>(); // Temporary variable int xorr = 0; // Using 2-pointers i, j int i = 0; for (int j = 0; j < N; j++) { // Expanding the window mp.put(A[j], mp.getOrDefault(A[j], 0) + 1); xorr = xorr ^ A[j]; // Shrinking the window while (mp.get(A[j]) > 1 || mp.size() > K) { int count = mp.get(A[i]); count--; if (count == 0) { mp.remove(A[i]); } else { mp.put(A[i], count); } xorr = xorr ^ A[i]; i++; } // If size of window is equal to K // then updating the mx variable if ((j - i + 1) == K) { mx = Math.max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct return mx; } // Driver function public static void main(String[] args) { // Size of given subarray int N = 10; // Given array A int[] A = {2, 3, 4, 2, 4, 5, 7, 4, 3, 9}; // Size of subarray needed int K = 4; // Function Call System.out.println("Maximum XOR of subarray of size K with all " + "distinct are: " + maximumXorsubarray(N, A, K)); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
C#
// C# code for the above approach:using System;using System.Collections.Generic;public class GFG { // Function performing Calculation static int maximumXorsubarray(int N, int[] A, int K) { // Variable for storing maximum XOR // of the subarray of size K int mx = -1; // Declaring map which is used for // storing frequencies Dictionary<int, int> mp = new Dictionary<int, int>(); // Temporary variable int xorr = 0; // Using 2-pointers i, j int i = 0; for (int j = 0; j < N; j++) { // Expanding the window if (mp.ContainsKey(A[j])) { mp[A[j]]++; } else { mp[A[j]] = 1; } xorr = xorr ^ A[j]; // Shrinking the window while (mp[A[j]] > 1 || mp.Count > K) { int count = mp[A[i]]; count--; if (count == 0) { mp.Remove(A[i]); } else { mp[A[i]] = count; } xorr = xorr ^ A[i]; i++; } // If size of window is equal to K // then updating the mx variable if ((j - i + 1) == K) { mx = Math.Max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct return mx; } static public void Main() { // Code // Size of given subarray int N = 10; // Given array A int[] A = { 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 }; // Size of subarray needed int K = 4; // Function Call Console.WriteLine( "Maximum XOR of subarray of size K with all " + "distinct are: " + maximumXorsubarray(N, A, K)); }}// This code is contributed by karthik. |
Python3
def maximumXorsubarray(N, A, K): # Variable for storing maximum XOR # of the subarray of size K mx = -1 # Declaring map which is used for # storing frequencies mp = {} # Temporary variable xorr = 0 # Using 2-pointers i, j i = 0 for j in range(N): # Expanding the window if A[j] not in mp: mp[A[j]] = 0 mp[A[j]] += 1 xorr ^= A[j] # Shrinking the window while mp[A[j]] > 1 or len(mp) > K: mp[A[i]] -= 1 xorr ^= A[i] if mp[A[i]] == 0: mp.pop(A[i]) i += 1 # If size of window is equal to K # then updating the mx variable if j - i + 1 == K: mx = max(mx, xorr) # Returning the Maximum XOR of subarray # of size K with all distinct return mx# Size of given subarrayN = 10# Given array AA = [2, 3, 4, 2, 4, 5, 7, 4, 3, 9]# Size of subarray neededK = 4# Function Callprint("Maximum XOR of subarray of size K with all " "distinct are: ", maximumXorsubarray(N, A, K)) |
Javascript
// JavaScript code for the above approach:function maximumXorsubarray(N, A, K){ // Variable for storing maximum XOR // of the subarray of size K let mx = -1; // Declaring map which is used for // storing frequencies let mp = new Map(); // Temporary variable let xorr = 0; // Using 2-pointers i, j let i = 0; for (let j = 0; j < N; j++) { // Expanding the window mp.set(A[j], (mp.get(A[j]) || 0) + 1); xorr ^= A[j]; // Shrinking the window while (mp.get(A[j]) > 1 || mp.size > K) { mp.set(A[i], mp.get(A[i]) - 1); xorr ^= A[i]; if (mp.get(A[i]) == 0) mp.delete(A[i]); i++; } // If size of window is equal to K // then updating the mx variable if (j - i + 1 == K) { mx = Math.max(mx, xorr); } } // Returning the Maximum XOR of subarray // of size K with all distinct elements return mx;}// Driver functionconst N = 10;// Given array Aconst A = [ 2, 3, 4, 2, 4, 5, 7, 4, 3, 9 ];// Size of subarray neededconst K = 4;// Function Callconsole.log("Maximum XOR of subarray of size K with all distinct elements is: " + maximumXorsubarray(N, A, K)); |
Output
Maximum XOR of subarray of size K with all distict are : 9
Time Complexity: O(N*Log(K))
Auxiliary Space: O(K)
