Given an array of integers, the task is to find maximum XOR value of a subarray of size K.
Examples :
Input : arr[] = {2, 5, 8 ,1 , 1 ,3} k = 3
Output : 15
Explanation : All subarrays of size k (=3) and
their XOR values are:
{2, 5, 8} => XOR value = 15
{5, 8, 1} => XOR value = 12
{8, 1, 1} => XOR value = 8
{1, 1, 3} => XOR value = 3
Maximum of all XOR values = 15
Input : arr[] = {1, 2, 4, 5, 6}
Output : 6
A simple solution is to consider all subarrays of size k one by one and compute XOR value. Finally return maximum of all XOR values. This solution takes O(n*k) time.
An efficient solution takes O(n) time. The idea is simple, we can find XOR value of current subarray of size k by removing first element of previous subarray and adding last element of current subarray. We can remove an element from current XOR by doing XOR of it again because of property of XOR that a ^ x ^ x = a.
Algorithm :
Let input array be 'arr[]' and size of array be 'n'
max_xor ; // user to store maximum xor value
current_xor; // user to store xor value of current subarray
// of size k
// First compute xor value of first subarray of size k
// (i goes from 0 to k)
corrent_xor = current_xor ^ arr[i]
// Initialize maximum XOR
max_xor = current_xor
Traversal rest array (i goes from k to n-1 )
a). remove first element of previous subarray
current_xor = current_xor ^ arr[i-k]
b). add new element to subarray
current_xor = current_xor ^ arr[i]
c). update max_xor = max(max_xor, current_xor)
return max_xor
Below is the implementation of above steps.
C++
// C++/C program to find maximum xor value of subarray of// size k#include<iostream>using namespace std;// Returns maximum XOR value of subarray of size kint maximumXOR(int arr[] , int n , int k){ // Compute XOR value of first subarray of size k int current_xor = 0 ; for (int i = 0 ; i < k ; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array int max_xor = current_xor; for (int i = k ; i < n; i++) { // First remove previous subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = max(max_xor, current_xor); } return max_xor;}// Driver programint main(){ int arr[] = {2, 5, 8 ,1 , 1 ,3} ; int k = 3; int n = sizeof(arr)/sizeof(arr[0]); cout << "Maximum XOR : " << maximumXOR(arr, n, k); return 0;} |
Java
// Java program to find maximum xor value of// subarray of size kimport java.io.*;class GFG { // Returns maximum XOR value of subarray of size k static int maximumXOR(int arr[] , int n , int k) { // Compute XOR value of first subarray of size k int current_xor = 0 ; for (int i = 0 ; i < k ; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array int max_xor = current_xor; for (int i = k ; i < n; i++) { // First remove previous subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = Math.max(max_xor, current_xor); } return max_xor; } // Driver program public static void main (String[] args) { int arr[] = {2, 5, 8 ,1 , 1 ,3} ; int k = 3; int n = arr.length; System.out.println( "Maximum XOR : " + maximumXOR(arr, n, k)); }}// This code is contributed by anuj_67. |
Python 3
# Python3 program to find maximum # xor value of subarray of# size# Returns maximum XOR value # of subarray of size kdef maximumXOR(arr , n , k): # Compute XOR value of first # subarray of size k current_xor = 0 for i in range ( k): current_xor = current_xor ^ arr[i] # Traverse rest of the array max_xor = current_xor for i in range( k,n): # First remove previous subarray's first # element current_xor = current_xor ^ arr[i-k] # add new element current_xor = current_xor ^ arr[i] # Update maximum xor value max_xor = max(max_xor, current_xor) return max_xor# Driver programif __name__ =="__main__": arr = [2, 5, 8 ,1 , 1 ,3] k = 3 n = len(arr) print ("Maximum XOR : " ,maximumXOR(arr, n, k))# This code is contributed by# ChitraNayal |
C#
// C# program to find maximum// xor value of subarray of // size kusing System;class GFG { // Returns maximum XOR value // of subarray of size k static int maximumXOR(int []arr, int n, int k) { // Compute XOR value of first // subarray of size k int current_xor = 0 ; for (int i = 0; i < k; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array int max_xor = current_xor; for (int i = k ; i < n; i++) { // First remove previous // subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = Math.Max(max_xor, current_xor); } return max_xor; } // Driver Code public static void Main () { int []arr = {2, 5, 8 ,1 , 1 ,3} ; int k = 3; int n = arr.Length; Console.WriteLine("Maximum XOR : " + maximumXOR(arr, n, k)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to find maximum // xor value of subarray of size k// Returns maximum XOR value// of subarray of size kfunction maximumXOR($arr, $n, $k){ // Compute XOR value of // first subarray of size k $current_xor = 0 ; for ($i = 0 ; $i < $k ; $i++) $current_xor = $current_xor ^ $arr[$i]; // Traverse rest of the array $max_xor = $current_xor; for ($i = $k ; $i < $n; $i++) { // First remove previous // subarray's first element $current_xor = $current_xor ^ $arr[$i - $k]; // add new element $current_xor = $current_xor ^ $arr[$i]; // Update maximum xor value $max_xor = max($max_xor, $current_xor); } return $max_xor;}// Driver Code$arr = array(2, 5, 8, 1, 1, 3) ;$k = 3;$n = sizeof($arr);echo "Maximum XOR : ", maximumXOR($arr, $n, $k);// This code is contributed by m_kit?> |
Javascript
<script>// Javascript program to find maximum xor value of// subarray of size k // Returns maximum XOR value of subarray of size k function maximumXOR(arr,n,k) { // Compute XOR value of first subarray of size k let current_xor = 0 ; for (let i = 0 ; i < k ; i++) current_xor = current_xor ^ arr[i]; // Traverse rest of the array let max_xor = current_xor; for (let i = k ; i < n; i++) { // First remove previous subarray's first // element current_xor = current_xor ^ arr[i-k]; // add new element current_xor = current_xor ^ arr[i]; // Update maximum xor value max_xor = Math.max(max_xor, current_xor); } return max_xor; } // Driver program let arr=[2, 5, 8 ,1 , 1 ,3]; let k = 3; let n = arr.length; document.write( "Maximum XOR : " + maximumXOR(arr, n, k)); // This code is contributed by rag2127</script> |
Output
Maximum XOR : 15
Time Complexity : O(n)
Auxiliary Space: O(1)
This article is contributed by Nishant_Singh(Pintu). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
