XOR of numbers that appeared even number of times in given Range
Given an array of numbers of size N and Q queries. Each query or a range can be represented by L (LeftIndex) and R(RightIndex). Find the XOR-sum of the numbers that appeared even number of times in the given range.
Prerequisite : Queries for number of distinct numbers in given range. | Segment Tree for range query
Examples :
Input : arr[] = { 1, 2, 1, 3, 3, 2, 3 }
Q = 5
L = 3, R = 6
L = 3, R = 4
L = 0, R = 2
L = 0, R = 6
L = 0, R = 4
Output : 0
3
1
3
2
Explanation of above example:
In Query 1, there are no numbers which appeared even number of times.
Hence the XOR-sum is 0.
In Query 2, {3} appeared even number of times. XOR-sum is 3.
In Query 3, {1} appeared even number of times. XOR-sum is 1.
In Query 4, {1, 2} appeared even number of times. XOR-sum is 1 xor 2 = 3.
In Query 5, {1, 3} appeared even number of times. XOR-sum is 1 xor 3 = 2.
Segment Trees or Binary Indexed Trees can be used to solve this problem efficiently.
Approach :
Firstly, it is easy to note that the answer for the query is the XOR-sum of all elements in the query range xor-ed with XOR-sum of distinct elements in the query range (since taking XOR of an element with itself results into a null value). Find the XOR-sum of all numbers in query range using prefix XOR-sums.
To find the XOR-sum of distinct elements in range : Number of distinct elements in a subarray of given range.
Now, returning back to our main problem, just change the assignment BIT[i] = 1 to BIT[i] = arri and count the XOR-sum instead of sum.
Below is the implementation using Binary Indexed Trees:
// CPP Program to Find the XOR-sum
// of elements that appeared even
// number of times within a range
#include <bits/stdc++.h>
using namespace std;
/* structure to store queries
L --> Left Bound of Query
R --> Right Bound of Query
idx --> Query Number */
struct que {
int L, R, idx;
};
// cmp function to sort queries
// according to R
bool cmp(que a, que b)
{
if (a.R != b.R)
return a.R < b.R;
else
return a.L < b.L;
}
/* N --> Number of elements present in
input array. BIT[0..N] --> Array that
represents Binary Indexed Tree*/
// Returns XOR-sum of arr[0..index]. This
// function assumes that the array is
// preprocessed and partial sums of array
// elements are stored in BIT[].
int getSum(int BIT[], int index)
{
// Initialize result
int xorSum = 0;
// index in BITree[] is 1 more than
// the index in arr[]
index = index + 1;
// Traverse ancestors of BIT[index]
while (index > 0)
{
// Take XOR of current element
// of BIT to xorSum
xorSum ^= BIT[index];
// Move index to parent node
// in getSum View
index -= index & (-index);
}
return xorSum;
}
// Updates a node in Binary Index Tree
// (BIT) at given index in BIT. The
// given value 'val' is xored to BIT[i]
// and all of its ancestors in tree.
void updateBIT(int BIT[], int N,
int index, int val)
{
// index in BITree[] is 1 more than
// the index in arr[]
index = index + 1;
// Traverse all ancestors and
// take xor with 'val'
while (index <= N)
{
// Take xor with 'val' to
// current node of BIT
BIT[index] ^= val;
// Update index to that of
// parent in update View
index += index & (-index);
}
}
// Constructs and returns a Binary Indexed
// Tree for given array of size N.
int* constructBITree(int arr[], int N)
{
// Create and initialize BITree[] as 0
int* BIT = new int[N + 1];
for (int i = 1; i <= N; i++)
BIT[i] = 0;
return BIT;
}
// Function to answer the Queries
void answeringQueries(int arr[], int N,
que queries[], int Q, int BIT[])
{
// Creating an array to calculate
// prefix XOR sums
int* prefixXOR = new int[N + 1];
// map for coordinate compression
// as numbers can be very large but we
// have limited space
map<int, int> mp;
for (int i = 0; i < N; i++) {
// If A[i] has not appeared yet
if (!mp[arr[i]])
mp[arr[i]] = i;
// calculate prefixXOR sums
if (i == 0)
prefixXOR[i] = arr[i];
else
prefixXOR[i] =
prefixXOR[i - 1] ^ arr[i];
}
// Creating an array to store the
// last occurrence of arr[i]
int lastOcc[1000001];
memset(lastOcc, -1, sizeof(lastOcc));
// sort the queries according to comparator
sort(queries, queries + Q, cmp);
// answer for each query
int res[Q];
// Query Counter
int j = 0;
for (int i = 0; i < Q; i++)
{
while (j <= queries[i].R)
{
// If last visit is not -1 update
// arr[j] to set null by taking
// xor with itself at the idx
// equal lastOcc[mp[arr[j]]]
if (lastOcc[mp[arr[j]]] != -1)
updateBIT(BIT, N,
lastOcc[mp[arr[j]]], arr[j]);
// Setting lastOcc[mp[arr[j]]] as j and
// updating the BIT array accordingly
updateBIT(BIT, N, j, arr[j]);
lastOcc[mp[arr[j]]] = j;
j++;
}
// get the XOR-sum of all elements within
// range using precomputed prefix XORsums
int allXOR = prefixXOR[queries[i].R] ^
prefixXOR[queries[i].L - 1];
// get the XOR-sum of distinct elements
// within range using BIT query function
int distinctXOR = getSum(BIT, queries[i].R) ^
getSum(BIT, queries[i].L - 1);
// store the final answer at the numbered query
res[queries[i].idx] = allXOR ^ distinctXOR;
}
// Output the result
for (int i = 0; i < Q; i++)
cout << res[i] << endl;
}
// Driver program to test above functions
int main()
{
int arr[] = { 1, 2, 1, 3, 3, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int* BIT = constructBITree(arr, N);
// structure of array for queries
que queries[5];
// Initializing values (L, R, idx) to queries
queries[0].L = 3;
queries[0].R = 6, queries[0].idx = 0;
queries[1].L = 3;
queries[1].R = 4, queries[1].idx = 1;
queries[2].L = 0;
queries[2].R = 2, queries[2].idx = 2;
queries[3].L = 0;
queries[3].R = 6, queries[3].idx = 3;
queries[4].L = 0;
queries[4].R = 4, queries[4].idx = 4;
int Q = sizeof(queries) / sizeof(queries[0]);
// answer Queries
answeringQueries(arr, N, queries, Q, BIT);
return 0;
}
import java.util.*;
// Class representing a query
class Query {
int L, R, idx; // Left Bound, Right Bound, Query Number
public Query(int L, int R, int idx) {
this.L = L;
this.R = R;
this.idx = idx;
}
}
// Main class
public class XORSumOfEvenOccurringElements {
// Comparator function to sort queries according to R
static class QueryComparator implements Comparator<Query> {
public int compare(Query a, Query b) {
if (a.R != b.R)
return a.R - b.R;
else
return a.L - b.L;
}
}
// Returns XOR-sum of elements in the array up to the given index
static int getSum(int[] BIT, int index) {
int xorSum = 0;
index += 1;
while (index > 0) {
xorSum ^= BIT[index];
index -= index & (-index);
}
return xorSum;
}
// Updates the Binary Indexed Tree (BIT) at the given index with the given value
static void updateBIT(int[] BIT, int index, int val) {
index += 1;
while (index < BIT.length) {
BIT[index] ^= val;
index += index & (-index);
}
}
// Constructs and returns a Binary Indexed Tree (BIT) for the given array
static int[] constructBITree(int[] arr) {
int[] BIT = new int[arr.length + 1];
Arrays.fill(BIT, 0);
return BIT;
}
// Answers the queries and prints the result
static void answeringQueries(int[] arr, Query[] queries, int[] BIT) {
int[] prefixXOR = new int[arr.length + 1];
Map<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (!mp.containsKey(arr[i]))
mp.put(arr[i], i);
if (i == 0)
prefixXOR[i] = arr[i];
else
prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
}
int[] lastOcc = new int[1000001];
Arrays.fill(lastOcc, -1);
Arrays.sort(queries, new QueryComparator());
int[] res = new int[queries.length];
int j = 0;
for (Query query : queries) {
while (j <= query.R) {
if (lastOcc[arr[j]] != -1)
updateBIT(BIT, lastOcc[arr[j]], arr[j]);
updateBIT(BIT, j, arr[j]);
lastOcc[arr[j]] = j;
j++;
}
int allXOR = prefixXOR[query.R] ^ (query.L == 0 ? 0 : prefixXOR[query.L - 1]);
int distinctXOR = getSum(BIT, query.R) ^ (query.L == 0 ? 0 : getSum(BIT, query.L - 1));
res[query.idx] = allXOR ^ distinctXOR;
}
for (int r : res) {
System.out.println(r);
}
}
// Main method
public static void main(String[] args) {
int[] arr = { 1, 2, 1, 3, 3, 2, 3 };
int N = arr.length;
int[] BIT = constructBITree(arr);
Query[] queries = {
new Query(3, 6, 0),
new Query(3, 4, 1),
new Query(0, 2, 2),
new Query(0, 6, 3),
new Query(0, 4, 4)
};
answeringQueries(arr, queries, BIT);
}
}
//Thus code is contributed by Kishan.
# Python program to Find the XOR-sum
# of elements that appeared even
# number of times within a range
# Class to store queries
class Query:
def __init__(self, L, R, idx):
self.L = L
self.R = R
self.idx = idx
# Function to sort queries according to R
def cmp(a, b):
if a.R != b.R:
return a.R < b.R
else:
return a.L < b.L
# Returns XOR-sum of arr[0..index]
def get_sum(BIT, index):
xor_sum = 0
index += 1
# Traverse ancestors of BIT[index]
while index > 0:
xor_sum ^= BIT[index]
index -= index & (-index)
return xor_sum
# Updates a node in Binary Index Tree (BIT)
def update_BIT(BIT, N, index, val):
index += 1
# Traverse all ancestors and xor with 'val'
while index <= N:
BIT[index] ^= val
index += index & (-index)
# Constructs and returns a Binary Indexed Tree for given array of size N
def construct_BITree(arr, N):
BIT = [0] * (N + 1)
return BIT
# Function to answer the Queries
def answering_queries(arr, N, queries, Q, BIT):
# Array to calculate prefix XOR sums
prefix_XOR = [0] * (N + 1)
# Map for coordinate compression
mp = {}
for i in range(N):
# If arr[i] has not appeared yet
if not mp.get(arr[i]):
mp[arr[i]] = i
# Calculate prefix XOR sums
if i == 0:
prefix_XOR[i] = arr[i]
else:
prefix_XOR[i] = prefix_XOR[i - 1] ^ arr[i]
# Array to store the last occurrence of arr[i]
last_occ = [-1] * 1000001
# Sort the queries according to the comparator
queries.sort(key=lambda x: (x.R, x.L))
# Answer for each query
res = [0] * Q
# Query Counter
j = 0
for i in range(Q):
while j <= queries[i].R:
# If last visit is not -1, update arr[j] to set null by taking xor with itself at the idx
# equal last_occ[mp[arr[j]]]
if last_occ[mp[arr[j]]] != -1:
update_BIT(BIT, N, last_occ[mp[arr[j]]], arr[j])
# Setting last_occ[mp[arr[j]]] as j and updating the BIT array accordingly
update_BIT(BIT, N, j, arr[j])
last_occ[mp[arr[j]]] = j
j += 1
# Get the XOR-sum of all elements within the range using precomputed prefix XOR sums
all_XOR = prefix_XOR[queries[i].R] ^ prefix_XOR[queries[i].L - 1]
# Get the XOR-sum of distinct elements within the range using BIT query function
distinct_XOR = get_sum(BIT, queries[i].R) ^ get_sum(BIT, queries[i].L - 1)
# Store the final answer at the numbered query
res[queries[i].idx] = all_XOR ^ distinct_XOR
# Output the result
for i in range(Q):
print(res[i])
# Driver program to test above functions
if __name__ == "__main__":
arr = [1, 2, 1, 3, 3, 2, 3]
N = len(arr)
BIT = construct_BITree(arr, N)
# Structure of array for queries
queries = [Query(3, 6, 0), Query(3, 4, 1), Query(0, 2, 2), Query(0, 6, 3), Query(0, 4, 4)]
Q = len(queries)
# Answer Queries
answering_queries(arr, N, queries, Q, BIT)
using System;
using System.Collections.Generic;
class Program
{
// Structure to store queries
struct Query
{
public int L, R, idx;
}
// Compare function to sort queries according to R
static int CompareQueries(Query a, Query b)
{
if (a.R != b.R)
return a.R.CompareTo(b.R);
else
return a.L.CompareTo(b.L);
}
// Returns XOR-sum of arr[0..index]
static int GetSum(int[] BIT, int index)
{
int xorSum = 0;
index = index + 1;
while (index > 0)
{
xorSum ^= BIT[index];
index -= index & (-index);
}
return xorSum;
}
// Updates a node in Binary Index Tree (BIT)
static void UpdateBIT(int[] BIT, int index, int val)
{
index = index + 1;
while (index < BIT.Length)
{
BIT[index] ^= val;
index += index & (-index);
}
}
// Constructs and returns a Binary Indexed Tree for the given array of size N
static int[] ConstructBITree(int[] arr, int N)
{
int[] BIT = new int[N + 1];
for (int i = 1; i <= N; i++)
BIT[i] = 0;
return BIT;
}
// Function to answer the Queries
static void AnsweringQueries(int[] arr, int N, Query[] queries, int Q, int[] BIT)
{
int[] prefixXOR = new int[N + 1];
Dictionary<int, int> mp = new Dictionary<int, int>();
for (int i = 0; i < N; i++)
{
if (!mp.ContainsKey(arr[i]))
mp[arr[i]] = i;
if (i == 0)
prefixXOR[i] = arr[i];
else
prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
}
int[] lastOcc = new int[1000001];
for (int i = 0; i < lastOcc.Length; i++)
lastOcc[i] = -1;
Array.Sort(queries, CompareQueries);
int[] res = new int[Q];
int j = 0;
for (int i = 0; i < Q; i++)
{
while (j <= queries[i].R)
{
if (lastOcc[mp[arr[j]]] != -1)
UpdateBIT(BIT, lastOcc[mp[arr[j]]], arr[j]);
UpdateBIT(BIT, j, arr[j]);
lastOcc[mp[arr[j]]] = j;
j++;
}
int allXOR = prefixXOR[queries[i].R] ^ (queries[i].L > 0 ? prefixXOR[queries[i].L - 1] : 0);
int distinctXOR = GetSum(BIT, queries[i].R) ^ (queries[i].L > 0 ? GetSum(BIT, queries[i].L - 1) : 0);
res[queries[i].idx] = allXOR ^ distinctXOR;
}
// Output the result
for (int i = 0; i < Q; i++)
Console.WriteLine(res[i]);
}
// Driver program to test above functions
static void Main()
{
int[] arr = { 1, 2, 1, 3, 3, 2, 3 };
int N = arr.Length;
int[] BIT = ConstructBITree(arr, N);
Query[] queries = new Query[5];
queries[0] = new Query { L = 3, R = 6, idx = 0 };
queries[1] = new Query { L = 3, R = 4, idx = 1 };
queries[2] = new Query { L = 0, R = 2, idx = 2 };
queries[3] = new Query { L = 0, R = 6, idx = 3 };
queries[4] = new Query { L = 0, R = 4, idx = 4 };
int Q = queries.Length;
AnsweringQueries(arr, N, queries, Q, BIT);
}
}
// Function to calculate XOR-sum
const getXOR = (arr, L, R) => {
let xorSum = 0;
for (let i = L; i <= R; i++) {
xorSum ^= arr[i];
}
return xorSum;
};
// Function to answer the Queries
const answeringQueries = (arr, N, queries) => {
// Creating an array to calculate prefix XOR sums
const prefixXOR = new Array(N + 1).fill(0);
// Creating an array to store the last occurrence of arr[i]
const lastOcc = new Array(1000001).fill(-1);
// answer for each query
const res = [];
// Query Counter
let j = 0;
for (let i = 0; i < queries.length; i++) {
while (j <= queries[i].R) {
if (lastOcc[arr[j]] !== -1) {
prefixXOR[lastOcc[arr[j]]] ^= arr[j];
}
prefixXOR[j] ^= arr[j];
lastOcc[arr[j]] = j;
j++;
}
// get the XOR-sum of all elements within range
const allXOR = prefixXOR[queries[i].R] ^ (queries[i].L > 0 ? prefixXOR[queries[i].L - 1] : 0);
// get the XOR-sum of distinct elements within range
const distinctXOR = getXOR(prefixXOR, queries[i].L, queries[i].R);
// store the final answer at the numbered query
res[queries[i].idx] = allXOR ^ distinctXOR;
}
// Output the result
for (let i = 0; i < res.length; i++) {
console.log(res[i]);
}
};
// Driver code to test above functions
const arr = [1, 2, 1, 3, 3, 2, 3];
const queries = [
{ L: 3, R: 6, idx: 0 },
{ L: 3, R: 4, idx: 1 },
{ L: 0, R: 2, idx: 2 },
{ L: 0, R: 6, idx: 3 },
{ L: 0, R: 4, idx: 4 }
];
answeringQueries(arr, arr.length, queries);
Output
0 3 1 3 2
Complexity Analysis:
- Time Complexity: O(Q * Log(N)), where N is the size of array, Q is the total number of queries.
- Space complexity: O(N) where N is size of array.
Approach : Using Mo’s Algorithm
- Sort the queries based on their left endpoints.
- Maintain a data structure to track the count of numbers in the current window.
- Process the queries one by one and update the count of numbers in the window accordingly, calculating the XOR-sum as needed.
Below is the implementation :
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// Function to count the occurrences of numbers in the array
int countOccurrences(vector<int>& arr, int left, int right)
{
unordered_map<int, int> count;
int xorSum = 0;
for (int i = left; i <= right; i++) {
count[arr[i]]++;
}
for (auto& entry : count) {
if (entry.second % 2 == 0) {
xorSum ^= entry.first;
}
}
return xorSum;
}
// Function to implement Mo's Algorithm
vector<int> moAlgorithm(vector<int>& arr,
vector<vector<int> >& queries)
{
int n = arr.size();
int m = queries.size();
// Sort the queries based on their left endpoints
sort(queries.begin(), queries.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
int left = 0, right = -1;
vector<int> xorSums(m);
unordered_map<int, int> count;
// Process the queries one by one
for (int i = 0; i < m; i++) {
int queryIndex = queries[i][2];
int queryLeft = queries[i][0];
int queryRight = queries[i][1];
// Extend the window to the right
while (right < queryRight) {
right++;
count[arr[right]]++;
}
// Shrink the window from the left
while (left > queryLeft) {
left--;
count[arr[left]]++;
}
// Shrink the window from the right
while (right > queryRight) {
count[arr[right]]--;
right--;
if (count[arr[right]] % 2 == 1) {
xorSums[queryIndex] ^= arr[right];
}
}
// Calculate the XOR sum for the current query range
xorSums[queryIndex]
^= countOccurrences(arr, queryLeft, queryRight);
}
return xorSums;
}
// Main method for testing
int main()
{
vector<int> arr = { 1, 2, 1, 3, 3, 2, 3 };
vector<vector<int> > queries = { { 3, 6, 0 },
{ 3, 4, 1 },
{ 0, 2, 2 },
{ 0, 6, 3 },
{ 0, 4, 4 } };
vector<int> result = moAlgorithm(arr, queries);
for (int res : result) {
cout << res << endl;
}
return 0;
}
import java.util.*;
public class MoAlgorithm {
// Function to count the occurrences of numbers in the
// array
private static int countOccurrences(int[] arr, int left,
int right)
{
Map<Integer, Integer> count = new HashMap<>();
int xorSum = 0;
for (int i = left; i <= right; i++) {
count.put(arr[i],
count.getOrDefault(arr[i], 0) + 1);
}
for (Map.Entry<Integer, Integer> entry :
count.entrySet()) {
if (entry.getValue() % 2 == 0) {
xorSum ^= entry.getKey();
}
}
return xorSum;
}
// Function to implement Mo's Algorithm
public static int[] moAlgorithm(int[] arr,
int[][] queries)
{
int n = arr.length;
int m = queries.length;
// Sort the queries based on their left endpoints
Arrays.sort(queries,
Comparator.comparingInt(a -> a[0]));
int left = 0, right = -1;
int[] xorSums = new int[m];
Map<Integer, Integer> count = new HashMap<>();
// Process the queries one by one
for (int[] query : queries) {
int queryIndex = query[2];
int queryLeft = query[0];
int queryRight = query[1];
// Extend the window to the right
while (right < queryRight) {
right++;
count.put(arr[right],
count.getOrDefault(arr[right], 0)
+ 1);
}
// Shrink the window from the left
while (left > queryLeft) {
left--;
count.put(arr[left],
count.getOrDefault(arr[left], 0)
+ 1);
}
// Shrink the window from the right
while (right > queryRight) {
count.put(arr[right],
count.get(arr[right]) - 1);
right--;
if (count.get(arr[right]) % 2 == 1) {
xorSums[queryIndex] ^= arr[right];
}
}
// Calculate the XOR sum for the current query
// range
xorSums[queryIndex] ^= countOccurrences(
arr, queryLeft, queryRight);
}
return xorSums;
}
// Main method for testing
public static void main(String[] args)
{
int[] arr = { 1, 2, 1, 3, 3, 2, 3 };
int[][] queries = { { 3, 6, 0 },
{ 3, 4, 1 },
{ 0, 2, 2 },
{ 0, 6, 3 },
{ 0, 4, 4 } };
int[] result = moAlgorithm(arr, queries);
for (int res : result) {
System.out.println(res);
}
}
}
// This code is contributed by Akshita
def mo_algorithm(arr, queries):
# Function to count the occurrences of numbers in the array
def count_occurrences(arr, left, right):
count = {}
xor_sum = 0
for i in range(left, right + 1):
count[arr[i]] = count.get(arr[i], 0) + 1
for num, freq in count.items():
if freq % 2 == 0:
xor_sum ^= num
return xor_sum
# Sort the queries based on their left endpoints
sorted_queries = sorted(enumerate(queries), key=lambda x: x[1][0])
# Initialize variables
left, right = 0, -1
xor_sums = [0] * len(queries)
count = {}
# Process the queries one by one
for query_index, (query_left, query_right) in sorted_queries:
# Extend the window to the right
while right < query_right:
right += 1
count[arr[right]] = count.get(arr[right], 0) + 1
# Shrink the window from the left
while left > query_left:
left -= 1
count[arr[left]] = count.get(arr[left], 0) + 1
# Shrink the window from the right
while right > query_right:
count[arr[right]] -= 1
right -= 1
if count[arr[right]] % 2 == 1:
xor_sums[query_index] ^= arr[right]
# Calculate the XOR sum for the current query range
xor_sums[query_index] ^= count_occurrences(
arr, query_left, query_right)
# Return output as newline-separated string
return '\n'.join(map(str, xor_sums))
# Example usage:
arr = [1, 2, 1, 3, 3, 2, 3]
queries = [(3, 6), (3, 4), (0, 2), (0, 6), (0, 4)]
result = mo_algorithm(arr, queries)
print(result)
function moAlgorithm(arr, queries) {
// Function to count the occurrences of numbers in the array
function countOccurrences(arr, left, right) {
let count = {};
let xorSum = 0;
for (let i = left; i <= right; i++) {
count[arr[i]] = (count[arr[i]] || 0) + 1;
}
for (let [num, freq] of Object.entries(count)) {
if (freq % 2 === 0) {
xorSum ^= parseInt(num);
}
}
return xorSum;
}
// Sort the queries based on their left endpoints
let sortedQueries = queries.slice().sort((a, b) => a[0] - b[0]);
// Initialize variables
let left = 0, right = -1;
let xorSums = new Array(queries.length).fill(0);
let count = {};
// Process the queries one by one
for (let [queryIndex, [queryLeft, queryRight]] of sortedQueries.entries()) {
// Extend the window to the right
while (right < queryRight) {
right++;
count[arr[right]] = (count[arr[right]] || 0) + 1;
}
// Shrink the window from the left
while (left > queryLeft) {
left--;
count[arr[left]] = (count[arr[left]] || 0) + 1;
}
// Shrink the window from the right
while (right > queryRight) {
count[arr[right]]--;
right--;
if (count[arr[right]] % 2 === 1) {
xorSums[queryIndex] ^= arr[right];
}
}
// Calculate the XOR sum for the current query range
xorSums[queryIndex] ^= countOccurrences(arr, queryLeft, queryRight);
}
// Return output as newline-separated string
return xorSums.join('\n');
}
// Example usage:
let arr = [1, 2, 1, 3, 3, 2, 3];
let queries = [[3, 6], [3, 4], [0, 2], [0, 6], [0, 4]];
let result = moAlgorithm(arr, queries);
console.log(result);
Output :
0
3
1
3
2
Complexity analysis :
Time Complexity: O((N+Q) N1/2) where N is the size of the array & Q is the number of queries.
Space complexity: O(N+Q)
Contact Us