Find the sum of all odd frequency elements in an array | faceprep

Program to find the sum of all odd frequency elements in an array is discussed here. An array of integers is given as input and the sum of elements having odd frequency is found and produced as output. 

This means elements which repeat an odd number of times in the given array will be identified and the sum of these will be the expected output.

For example, consider an array arr = {1, 2, 4, 5, 6, 3, 1, 2, 3, 3}

Here, elements 1 and 2 repeats twice (even), whereas elements 4, 5, 6 are present only once (odd) and element 3 occurs thrice (odd). Hence,

  • Elements having odd frequency : {4, 5, 6, 3, 3, 3}
  • Sum of elements having odd frequency: 24

Algorithm

  • Traverse the array from the beginning.
  • Store the frequency of elements in the array using maps in C++ with the array element in one column and its frequency in the other column.
  • Now, find the elements having an odd frequency.
  • Calculate the sum of elements having an odd frequency and return the sum.

Program to find the sum of all odd frequency elements in an array

// C++ program to find the sum of all odd frequency elements in an array

#include <bits/stdc++.h>
using namespace std;
int sum(int a[], int len);
int main()
{
int a[20], len, i;
scanf(“%d”, &len);
for(i=0; i<len; i++)
{
scanf(“%d”, &a[i]);
}
cout << sum(a, len);
return 0;
}
int sum(int a[], int len)
{
// Store frequencies of elements of the array
unordered_map<int, int> m;
for (int i = 0; i < len; i++)
m[a[i]]++;

// variable to store sum of all odd occurring elements
int sum = 0;

// loop to iterate through map
for (auto itr = m.begin(); itr != m.end(); itr++) {

// check if frequency is odd
if (itr->second % 2 != 0)
sum += (itr->first) * (itr->second);
}
return sum;
}

# Python program to find the sum of all odd frequency elements in an array

import collections

def findsum(arr, N):
mp = collections.defaultdict(int)

for i in range(N):
mp[arr[i]] += 1

sum = 0

for i in mp:

# Check if frequency is odd
if (mp[i] % 2 != 0):
sum += (i * mp[i])
return sum

arr = [ 1, 2, 4, 5, 6, 3, 1, 2, 3, 3 ]
N = len(arr)
print (findsum(arr, N))

Output:

sum of all odd frequency elements

Time complexity: O(n)