**Introduction**

One day, ninja's teacher gave him an assignment in which he had an array ‘ARR’ of size ‘N’ and had to process ‘Q’ queries. In each query, he has given ‘L’ and ‘R’ (L <= R <= N), and For each query, his task is to print the sum of all elements with odd frequency in range ‘L’ to ‘R’. Help ninja to pass the assignment.

The above problem is the variation of the standard range query problem. Range queries based-coding problems are widely asked in coding contests and various coding interviews.

In this blog, we will solve the above problem using a range query approach.

**The Problem Statement**

Given an array ‘ARR’ of size ‘N’. You have to process ‘Q’ queries. For each query, you are given ‘L’ and ‘R’ (L <= R <=N). Your task is to print the sum of all elements with odd frequency in the subarray ‘L’ to ‘R’ of ‘ARR’.

**Example**

Suppose, ARR = {3, 2, 1, 4, 4, 5, 3, 2, 1}. Q = 2, the queries are given as:

- L = 1 and R = 5, so here we need to calculate our result in {3, 2, 1, 4, 4}. The frequency of 1, 2 and 3 is 1, which is odd whereas the frequency of 4 is 2 which is even. Hence the sum of elements with odd frequency is 3 + 2 + 1 =
**6.** - L = 2 and R = 8, so here we need to calculate our result in {2, 1, 4, 4, 5, 3, 2}. The frequency of 1, 5 and 3 is 1 which is odd, whereas the frequency of 4 and 2 is two, which is even. Hence the sum of elements with odd frequency is 1 + 5 + 3 =
**9**.

Check out __Euclid GCD Algorithm__