Sum of All Elements With Odd Frequency in the Given Subarray

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)
{

    // To store the answer.
    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!