Practice Problems on Prefix Xor Array
Problem | Practice Link |
---|---|
solve | |
XOR of a given range | solve |
XOR of all elements | solve |
solve | |
solve | |
solve | |
Game of xor | solve |
solve | |
solve |
Prefix Xor Array
Given an array arr[] of size N, find the Prefix Xor of the array. A prefix xor array is another array prefixXor[] of the same size, such that the value of prefixXor[i] is arr[0] ^ arr[1] ^ arr[2] . . . arr[i].
Examples:
Input: arr[] = {10, 20, 10, 5, 15}
Output: prefixXor[] = {10, 30, 20, 17, 30 }
Explanation: While traversing the array, update the element by xoring it with its previous element.
prefixXor[0] = 10,
prefixXor[1] = prefixXor[0] ^ arr[1] = 30,
prefixXor[2] = prefixXor[1] ^ arr[2] = 20 and so on.Input: arr[]={1,2,1,2,5}
Output: prefixXor[] = {1, 3, 2, 0, 5 }
Approach: To solve the problem follow the given steps:
- Declare a new array prefixXor[] of the same size as the input array
- Run a for loop to traverse the input array
- For each index add the value of the current element and the previous value of the prefix sum array
Below is the implementation of the approach:
// C++ program for Implementing prefix sum array
#include <bits/stdc++.h>
using namespace std;
// Fills prefix sum array
void PrefixXor(int arr[], int n, int preXor[])
{
preXor[0] = arr[0];
// Xoring present element with previous element
for (int i = 1; i < n; i++)
preXor[i] = preXor[i - 1] ^ arr[i];
}
// Driver Code
int main()
{
int arr[] = { 10, 20, 10, 5, 15 };
int n = sizeof(arr) / sizeof(arr[0]);
int preXor[n];
// Function call
PrefixXor(arr, n, preXor);
cout << "Given Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "Prefix Xor: ";
for (int i = 0; i < n; i++)
cout << preXor[i] << " ";
}
public class PrefixXor {
// Fills prefix XOR array
static void prefixXor(int[] arr, int n, int[] preXor)
{
preXor[0] = arr[0];
// Xoring present element with the previous element
for (int i = 1; i < n; i++) {
preXor[i] = preXor[i - 1] ^ arr[i];
}
}
public static void main(String[] args)
{
int[] arr = { 10, 20, 10, 5, 15 };
int n = arr.length;
int[] preXor = new int[n];
// Function call
prefixXor(arr, n, preXor);
System.out.print("Given Array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.print("Prefix XOR: ");
for (int i = 0; i < n; i++) {
System.out.print(preXor[i] + " ");
}
}
}
def prefix_xor(arr, n, pre_xor):
pre_xor[0] = arr[0]
# Xoring present element with the previous element
for i in range(1, n):
pre_xor[i] = pre_xor[i - 1] ^ arr[i]
if __name__ == "__main__":
arr = [10, 20, 10, 5, 15]
n = len(arr)
pre_xor = [0] * n
# Function call
prefix_xor(arr, n, pre_xor)
print("Given Array:", end=" ")
for i in range(n):
print(arr[i], end=" ")
print()
print("Prefix XOR:", end=" ")
for i in range(n):
print(pre_xor[i], end=" ")
using System;
class PrefixXorExample
{
// Fills prefix sum array
static void PrefixXor(int[] arr, int n, int[] preXor)
{
preXor[0] = arr[0];
// Xoring present element with previous element
for (int i = 1; i < n; i++)
preXor[i] = preXor[i - 1] ^ arr[i];
}
// Driver Code
static void Main()
{
int[] arr = { 10, 20, 10, 5, 15 };
int n = arr.Length;
int[] preXor = new int[n];
// Function call
PrefixXor(arr, n, preXor);
Console.Write("Given Array: ");
foreach (int item in arr)
{
Console.Write(item + " ");
}
Console.WriteLine();
Console.Write("Prefix Xor: ");
foreach (int item in preXor)
{
Console.Write(item + " ");
}
}
}
// Fills prefix sum array
function prefixXor(arr) {
const n = arr.length;
const preXor = Array(n);
preXor[0] = arr[0];
// Xoring present element with previous element
for (let i = 1; i < n; i++) {
preXor[i] = preXor[i - 1] ^ arr[i];
}
return preXor;
}
// Driver Code
function main() {
const arr = [10, 20, 10, 5, 15];
const n = arr.length;
// Function call
const preXor = prefixXor(arr);
console.log("Given Array:", arr.join(" "));
console.log("Prefix Xor:", preXor.join(" "));
}
// Run the main function
main();
Output
Given Array: 10 20 10 5 15 Prefix Xor: 10 30 20 17 30
Time Complexity: O(N), where N is the size of input array
Auxiliary Space: O(N)