Given an array of integers containing duplicate elements. The task is to find the sum of all even occurring elements in the given array. That is the sum of all such elements whose frequency is even in the array.
Examples:
Input : arr[] = {1, 1, 2, 2, 3, 3, 3}
Output : 6
The even occurring element are 1 and 2 (both occur two times).
Therefore sum of all 1's in the array = 1+1+2+2 = 6.
Input : arr[] = {10, 20, 30, 40, 40}
Output : 80
Element with even frequency are 40.
Sum = 40.
Approach:
- Traverse the array and use a unordered_map in C++ to store the frequency of elements of the array such that the key of map is the array element and value is its frequency in the array.
- Then, traverse the map to find the frequency of elements and check if it is even, if it is even, then add this element to sum.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findSum(int arr[], int N)
{
unordered_map<int, int> mp;
for (int i = 0; i < N; i++) {
mp[arr[i]]++;
}
int sum = 0;
for (auto itr = mp.begin(); itr != mp.end(); itr++) {
if (itr->second % 2 == 0)
sum += (itr->first) * (itr->second);
}
return sum;
}
int main()
{
int arr[] = { 10, 20, 20, 40, 40 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findSum(arr, N);
return 0;
}
|
Java
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class GFG {
public static int element(int[] arr, int n)
{
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
int count = 0;
if (map.get(arr[i]) != null) {
count = map.get(arr[i]);
}
map.put(arr[i], count + 1);
}
int sum = 0;
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() % 2 == 0) {
sum += entry.getKey() * entry.getValue();
}
}
return sum;
}
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 2, 3, 3, 3 };
int n = arr.length;
System.out.println(element(arr, n));
}
}
|
Python3
def findSum(arr, N):
mp = {}
for i in range(N):
if arr[i] in mp:
mp[arr[i]] += 1
else:
mp[arr[i]] = 1
Sum = 0
for first, second in mp.items():
if (second % 2 == 0):
Sum += (first) * (second)
return Sum
arr = [ 10, 20, 20, 40, 40 ]
N = len(arr)
print(findSum(arr, N))
|
C#
using System;
using System.Collections.Generic;
class GFG {
static int element(int[] arr, int n)
{
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
if(!map.ContainsKey(arr[i]))
{
map.Add(arr[i], 1);
}
else
{
map[arr[i]] += 1;
}
}
int sum = 0;
foreach(KeyValuePair<int, int> entry in map)
{
if (entry.Value % 2 == 0)
{
sum += entry.Key * entry.Value;
}
}
return sum;
}
static void Main() {
int[] arr = { 10, 20, 20, 40, 40};
int n = arr.Length;
Console.WriteLine(element(arr, n));
}
}
|
Javascript
<script>
function findSum(arr, N)
{
let mp = new Map();
for (let i = 0; i < N; i++) {
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1)
} else {
mp.set(arr[i], 1)
}
}
let sum = 0;
for (let itr of mp) {
if (itr[1] % 2 == 0)
sum += (itr[0]) * (itr[1]);
}
return sum;
}
let arr = [10, 20, 20, 40, 40];
let N = arr.length
document.write(findSum(arr, N));
</script>
|
Time Complexity: O(N), where N is the number of elements in the array.
Auxiliary Space: O(N)
Method 2: Using Built-in python functions:
- Count the frequencies of every element using Counter function
- Traverse the frequency dictionary and sum all the elements with occurrence even frequency multiplied by its frequency.
Below is the implementation:
C++
#include <iostream>
#include <unordered_map>
using namespace std;
void sumEven(int arr[], int n)
{
unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
freq[arr[i]]++;
}
int sum = 0;
for (auto it : freq) {
if (it.second % 2 == 0) {
sum = sum + it.first * it.second;
}
}
cout << sum << endl;
}
int main()
{
int arr[] = { 10, 20, 20, 40, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
sumEven(arr, n);
return 0;
}
|
Java
import java.util.*;
public class Main {
public static void sumEven(int[] arr, int n)
{
Map<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < n; i++) {
freq.put(arr[i],
freq.getOrDefault(arr[i], 0) + 1);
}
int sum = 0;
for (Map.Entry<Integer, Integer> entry :
freq.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
if (value % 2 == 0) {
sum += key * value;
}
}
System.out.println(sum);
}
public static void main(String[] args)
{
int[] arr = { 10, 20, 20, 40, 40 };
int n = arr.length;
sumEven(arr, n);
}
}
|
Python3
from collections import Counter
def sumEven(arr, n):
freq = Counter(arr)
sum = 0
for it in freq:
if freq[it] % 2 == 0:
sum = sum + it*freq[it]
print(sum)
arr = [10, 20, 20, 40, 40]
n = len(arr)
sumEven(arr, n)
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
static void Main(string[] args)
{
int[] arr = { 10, 20, 20, 40, 40 };
int n = arr.Length;
sumEven(arr, n);
}
static void sumEven(int[] arr, int n)
{
Dictionary<int, int> freq
= arr.GroupBy(x = > x).ToDictionary(
g = > g.Key, g = > g.Count());
int sum = 0;
foreach(KeyValuePair<int, int> pair in freq)
{
if (pair.Value % 2 == 0) {
sum += pair.Key * pair.Value;
}
}
Console.WriteLine(sum);
}
}
|
Javascript
function sumEven(arr)
{
let freq = {};
for (let i = 0; i < arr.length; i++) {
if (freq[arr[i]] === undefined) {
freq[arr[i]] = 1;
} else {
freq[arr[i]]++;
}
}
let sum = 0;
for (let key in freq) {
if (freq[key] % 2 == 0) {
sum = sum + key * freq[key];
}
}
console.log(sum);
}
let arr = [10, 20, 20, 40, 40];
sumEven(arr);
|
Time complexity: O(n) where n is size of given list “arr”
Auxiliary space: O(1)
Approach#3:using pointers
Algorithm
1. Sort the input array arr.
2. Initialize two pointers i and j to 0.
3. Initialize a variable sum to 0.
4.While j < len(arr):
a. If arr[j] is equal to arr[i], increment j.
b. Otherwise, if (j – i) % 2 == 0, add arr[i] * (j – i) to sum.
c. Set i to j.
5.If (j – i) % 2 == 0, add arr[i] * (j – i) to sum.
6. Return sum.
C++
#include <iostream>
#include <vector>
#include <algorithm> // Required for sorting
using namespace std;
int sumEvenFreq(vector<int>& arr) {
sort(arr.begin(), arr.end());
int i = 0, j = 0;
int sum = 0;
while (j < arr.size()) {
if (arr[j] == arr[i]) {
j++;
} else {
if ((j - i) % 2 == 0) {
sum += arr[i] * (j - i);
}
i = j;
}
}
if ((j - i) % 2 == 0) {
sum += arr[i] * (j - i);
}
return sum;
}
int main() {
vector<int> arr = {10, 20, 30, 40, 40};
cout << "Sum of elements with even frequency: " << sumEvenFreq(arr) << endl;
return 0;
}
|
Java
import java.util.Arrays;
public class Main {
static int sumEvenFreq(int[] arr) {
Arrays.sort(arr);
int i = 0, j = 0;
int sum = 0;
while (j < arr.length) {
if (arr[j] == arr[i]) {
j++;
} else {
if ((j - i) % 2 == 0) {
sum += arr[i] * (j - i);
}
i = j;
}
}
if ((j - i) % 2 == 0) {
sum += arr[i] * (j - i);
}
return sum;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 40};
System.out.println("Sum of elements with even frequency: " + sumEvenFreq(arr));
}
}
|
Python3
def sum_even_freq(arr):
arr.sort()
i = j = 0
sum = 0
while j < len(arr):
if arr[j] == arr[i]:
j += 1
else:
if (j - i) % 2 == 0:
sum += arr[i] * (j - i)
i = j
if (j - i) % 2 == 0:
sum += arr[i] * (j - i)
return sum
arr = [ 10, 20, 30, 40, 40 ]
print(sum_even_freq(arr))
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int SumEvenFreq(List<int> arr)
{
arr.Sort();
int i = 0, j = 0;
int sum = 0;
while (j < arr.Count)
{
if (arr[j] == arr[i])
{
j++;
}
else
{
if ((j - i) % 2 == 0)
{
sum += arr[i] * (j - i);
}
i = j;
}
}
if ((j - i) % 2 == 0)
{
sum += arr[i] * (j - i);
}
return sum;
}
static void Main()
{
List<int> arr = new List<int> { 10, 20, 30, 40, 40 };
Console.WriteLine("Sum of elements with even frequency: " + SumEvenFreq(arr));
}
}
|
Javascript
function sum_even_freq(arr) {
arr.sort();
let i = 0;
let j = 0;
let sum = 0;
while (j < arr.length) {
if (arr[j] == arr[i]) {
j += 1;
} else {
if ((j - i) % 2 == 0) {
sum += arr[i] * (j - i);
}
i = j;
}
}
if ((j - i) % 2 == 0) {
sum += arr[i] * (j - i);
}
return sum;
}
let arr = [10, 20, 30, 40, 40];
console.log(sum_even_freq(arr));
|
Time complexity: O(n log n), where n is the length of the input array arr. The sort() function takes O(n log n) time in the worst case, and the while loop takes O(n) time to iterate through the sorted array. Therefore, the overall time complexity is dominated by the sort() function.
Space complexity: O(1), since we’re using a constant amount of extra space to store the pointers i and j, and the variable sum.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
