1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Sum of All Elements With Odd Frequency in the Given Subarray

Ujjawal Gupta
0 upvote

## 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

## Approach

The naive approach to solving the above problem is to iterate all elements in the subarray from ‘L’ to ‘R’ and check whether the element’s frequency is even or odd. If it is odd, add it in the final answer; otherwise, leave it. The algorithm of the above approach is discussed below.

### Algorithm

• Define a function getOddFrequentSum(‘ARR’ , ‘L’ , ‘R’):
• Function Description:
• It takes ‘ARR’, ‘L’, and ‘R’ as parameters.
• It returns the sum of all elements with odd frequency in the subarray.
• Function Working:
• Create a variable ANS = 0.
• Iterate loop from i = L - 1 to i < R:
• Create variable FREQUENCY = 0.
• Iterate loop j = L - 1 to j < R:
• If ARR[i] == ARR [j]:
• FREQUENCY++.
• If ‘FREQUENCY’ is odd:
• ANS += ARR[i].
• Return ‘ANS’.
• Call the function getOddFrequentSum() for each query.

### Program

``````#include <iostream>
#include <vector>
using namespace std;

// Function to get the sum of all elements with odd frequency.
int getOddFrequentSum(vector<int> &vec, int l, int r)
{

int ans = 0;
for (int i = l - 1; i < r; i++)
{

// To store the frequency.
int frequency = 0;
for (int j = l - 1; j < r; j++)
{
if (vec[i] == vec[j])
{
frequency++;
}
}

// Check whether the frequency is odd or not.
if (frequency % 2 == 1)
{
ans += vec[i];
}
}
return ans;
}
int main()
{

// Taking 'N' number of elements in array as an input.
int n;
cin >> n;

// Taking elements of an array as an input.
vector<int> vec(n);
for (int i = 0; i < n; i++)
{
cin >> vec[i];
}

// Number of queries.
int q;
cin >> q;
while (q--)
{

// Taking 'L' and 'R' as as input/.
int l, r;
cin >> l >> r;

// Function Call.
int ans = getOddFrequentSum(vec, l, r);
cout << ans << endl;
}
return 0;
}``````

### Input

``````9
3 2 1 4 4 5 3 2 1
2
1 5
2 8``````

### Output

``````6
9``````

### Time Complexity

O(Q * N^2), where ‘N’ is the size of an array and ‘Q’ is the number of queries.
For each query, the calculation of the frequency of each element takes O(R - L + 1) = O(N) time. So, for all the elements elements, it is O(N^2). There are total ‘Q’ queries; hence the total time complexity is O(Q * N^2).

### Space Complexity

O(1).
As we didn’t use extra space except for a few variables.

## Key Takeaways

In this blog, we learned about an interesting problem, namely sum of all elements with odd frequency in the given subarray. We have discussed the brute force approach. The brute force approach is always first to go. We saw the time complexity of the approach is O(Q * N^2).

Check out this problem - Subarray With 0 Sum

Hence 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 Coding!

Live masterclass