1.
Introduction
2.
Problem Statement
2.1.
INPUT
2.2.
OUTPUT
2.3.
Explanation
3.
Approach
3.1.
Program
3.2.
INPUT
3.3.
OUTPUT
3.4.
Time Complexity
3.5.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# XOR of Numbers that Appeared Even Number of Times in Given Range

0 upvote

## Introduction

In this blog, we will discuss a problem based on Fenwick Tree. Fenwick tree is an advanced data structure used to solve range-based queries. It supports query (prefix sum calculations) and updates in logarithmic time complexity. It can be built or preprocessed in linear time. We will solve the given problem efficiently using the Binary Indexed Tree.

## Problem Statement

Ninja has been given an array A[ ] of size N and Q queries. Each query is a range of the form [L, R]. Your task is to find the XOR-sum of the numbers that appeared an even number of times in the given interval for each query.

### INPUT

N = 7

A[ ] = {1, 2, 1, 3, 3, 2, 3}

Q = 5

Queries[ ] = [{3, 6}, {3, 4}, {0, 2}, {0, 6}, {0, 4} ]

0

3

1

3

2

### Explanation

Query1: Xor-sum is zero because no number occurred an even number of times.

Query2: Xor-sum is 3 because the number which occurred an even number of times is {3}.

Query3: Xor-sum is 1 because the number which occurred an even number of times is {1}.

Query4: Xor-sum is 3 because numbers that occurred even number of times are {1, 2}.

Query5: Xor-sum is 2 because numbers that occurred even number of times are {1, 3}.

## Approach

Observation: The answer to the query is:

queryAns = (XOR-sum of all number between{L to R}) (XOR-sum of distinct numbers between{L to R})

We need to find the XOR-sum of numbers that appeared an even number of times in a given range. Two important properties of XOR are (a^a=0) and (a^0=a).

Here XOR-sum of all numbers will give the XOR of all numbers that appeared an odd number of times in the range {L to R} (Because even times occurring elements will cancel out due to a^a=0 property).

And XORing this all numbers that appeared an odd number of times with all distinct numbers in that range will give us numbers that appeared an even number of times (this time odd time appearing elements will cancel out).

Efficient: XOR-sum of all numbers in the query range can be calculated using the prefix Xor-sums. And xor-sum of all distinct numbers in a range can be found by using Binary Indexed Tree through the following steps:

i)   Create an array lastOccured[ ] and initialize it with -1. Here lastOccured[a[i]] holds the rightmost index of the number a[i] in the array ‘a’.

ii)  Sort all queries according to the right index ‘R’ in ascending order.

iii) Create a BIT[ ] array and initialize it with all 0s (Binary Indexed Tree).

iv) Iterate over the input array. Also, keep a pointer for queries.

a. Check a[i] has been visited earlier i.e, if lastOccured[a[i]] == -1 or not. If not, update Binary Indexed Tree at the index lastOccured[a[i]] with value -1.

b. Update lastOccured[a[i]] = i and update Binary Indexed Tree at the index with value a[i].

c. Now answer queries where R = i by using querying Binary Indexed Tree.

### Program

``````#include <bits/stdc++.h>
using namespace std;

#define MAXSIZE 1000001

// For storing queries.
typedef struct {
int L;
int R;
int idx;
} query;

// Custom comparator to sort queries in
// ascending order according to R.
bool CustomComparator(query &a, query &b){
if(a.R == b.R)
return a.L < b.L;

return a.R < b.R;
}

/*--------------- BINARY INDEXED TREE. //BEGINS -----------*/
vector<int>BIT;

/**
* @brief This is a utility function which calculate
* the sum of array[0 ... idx] using the BIT data structure.
*
* @param idx Index tree node.
* @return int
*/
int Sum(int idx){
int _sum = 0;

/* Traversing the ancestors of idx node. */
while(idx > 0){
_sum ^= BIT[idx]; // Add current element in count.

idx -= (idx & -idx); // Move to 'sum' parent node.
}
// Return count of smaller element on the right side.
return _sum;
}

/**
* @brief This function updates a node of Binary Indexed Tree(BIT)
* at given index 'idx'. Given value 'change' is added to BIT[idx] node
* and its ancestors.
*
* @param idx Index tree node.
* @param change Effective difference that needs to be updated.
* @return void
*/
void Update(int idx, int change){

/* Traverse over all ancestors of BIT[idx] and add 'change' */
while(idx < BIT.size()){
BIT[idx] ^= change; // Add 'change' in current node.

idx += (idx & -idx); // Move to 'update' parent node.
}
}
/*--------------- BINARY INDEXED TREE. //ENDS   -----------*/

void solve(vector<int> &a, int N, query queries[], int Q){
// Initialize BIT.
BIT.clear();
BIT.resize(N+1, 0);

// Array for storing prefix XOR sums.
int prefixXOR[N+1];
memset(prefixXOR, 0, sizeof(prefixXOR));

/* for coordinate compression (because the number can be very
large but we have limited space.)*/
map<int, int>mp;

for(int i=0; i<N; i++){
// Update in map if a[i] has not appeared yet.
if(!mp[a[i]])
mp[a[i]] = i;

// pre-calculating prefix XOR sums;
if(i == 0)
prefixXOR[i] = a[i];
else
prefixXOR[i] = prefixXOR[i-1] ^ a[i];
}

/* Array to store last occurence of a[i] */
int lastOcc[MAXSIZE];
memset(lastOcc, -1, sizeof(lastOcc));

/* Sort the queries in ascending order according to R */
sort(queries, queries+Q, CustomComparator);

// To store the final answer for each query.
int finalAns[Q];

// will be used as a query counter.
int j = 0;

for(int i=0; i<Q; i++){

while(j <= queries[R]){
/* If lastOcc[mp[a[j]] is not -1, set null
in a[j] by xoring it with itself at the
idx equal lastOcc[mp[a[j]] */
if(lastOcc[mp[a[j]]] != -1)
Update(lastOcc[mp[a[j]]]+1, a[j]);

/* Updating the BIT array and setting
lastOcc[mp[a[j]]] as j */
Update(j+1, a[j]);
lastOcc[mp[a[j]]] = j++;
}

/* Calculate the XOR-sum of all element within the
range of query using precomputed prefix XORsums */
int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];

/* Calculate the XOR-sum of distinct elements within the
range of query using Binary Indexed Tree */
int distinctXOR = Sum(queries[i].R+1) ^ Sum(queries[i].L);

finalAns[queries[i].idx] = allXOR ^ distinctXOR;
}

for(int i=0; i<Q; i++)
cout << finalAns[i] << endl;
}

// Driver Function.
int main(){
int tt = 1;
cin >> tt;
while(tt--){
int N; cin >> N;

vector<int>a(N);
for(int i=0; i<N; i++)cin >> a[i];

int Q; cin >> Q;
query queries[Q];
for(int i=0; i<Q; i++){
cin >> queries[i].L >> queries[i].R;
queries[i].idx = i;
}

solve(a, N, queries, Q);
}
return 0;
}
``````

### INPUT

``````1
7
1 2 1 3 3 2 3
5
3 6
3 4
0 2
0 6
0 4``````

### OUTPUT

``````0
3
1
3
2``````

### Time Complexity

The time complexity of the above approach is O(Q * log(N)), where Q is the number of queries and N is the size of the input array.

### Space Complexity

The auxiliary space complexity of the program is O(N).

Check out this problem - Count Inversions

## FAQs

1. What is Fenwick Tree or Binary Indexed Tree?
A Fenwick tree or Binary Indexed Tree is a data structure that allows efficient calculations of prefix sums and efficient updates of elements in the array (while retaining tree structure & all its properties).

2. What is the time complexity of insertion and query in a Fenwick Tree or Binary Indexed Tree?
The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).

3. What is the advantage of Fenwick tree over Segment tree?
The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.

4. What is the disadvantage of the Fenwick tree over the Segment tree?
We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

## Key Takeaways

Cheers if you reached here!!

This article discussed an intriguing problem using the Fenwick Tree or Binary Indexed Tree. Fenwick Tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!

Live masterclass