Given an array arr[] of integers, the task is to find the absolute difference between the sum of all odd frequent array elements and the sum of all even frequent array elements.
Examples:
Input: arr[] = {1, 5, 5, 2, 4, 3, 3}
Output: 9
Explanation:
The even frequent elements are 5 and 3 (both occurring twice).
Therefore, sum of all even frequent elements = 5 + 5 + 3 + 3 = 16.
The odd frequent elements are 1, 2 and 4 (each occurring once).
Therefore, sum of all odd frequent elements = 1 + 2 + 4 = 7.
Difference between their sum = 16 – 7 = 9.Input: arr[] = {1, 1, 2, 2, 3, 3}
Output: 12
Explanation:
The even frequent array elements are 1, 2 and 3 (occurring twice).
Therefore, sum of all even frequent elements = 12.
Since there is no odd frequent element present in the array, difference = 12 – 0 = 12
Approach: Follow the steps below to solve the problem:
- Initialize an unordered_map to store the frequency of array elements.
- Traverse the array and update the frequency of array elements in the Map.
- Then, traverse the map and add the elements having even frequency to a variable, say sum_even, and the ones with odd frequencies to another variable, say sum_odd.
- Finally, print the difference between sum_odd and sum_even.
Below is the implementation of the above approach:
C++
// C++ program to find absolute difference // between the sum of all odd frequent and // even frequent elements in an array #include <bits/stdc++.h> using namespace std; // Function to find the sum of all even // and odd frequent elements in an array int findSum(int arr[], int N) { // Stores the frequency of array elements unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of // current element mp[arr[i]]++; } // Stores sum of odd and even // frequent elements int sum_odd = 0, sum_even = 0; // Traverse the map for (auto itr = mp.begin(); itr != mp.end(); itr++) { // If frequency is odd if (itr->second % 2 != 0) // Add sum of all occurrences of // current element to sum_odd sum_odd += (itr->first) * (itr->second); // If frequency is even if (itr->second % 2 == 0) // Add sum of all occurrences of // current element to sum_even sum_even += (itr->first) * (itr->second); } // Calculate difference // between their sum int diff = sum_even - sum_odd; // Return diff return diff; } // Driver Code int main() { int arr[] = { 1, 5, 5, 2, 4, 3, 3 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findSum(arr, N); return 0; } |
Java
// Java program to find absolute difference // between the sum of all odd frequent and // even frequent elements in an array import java.util.*;import java.io.*;import java.math.*;class GFG{ // Function to find the sum of all even // and odd frequent elements in an array static int findSum(int arr[], int N) { // Stores the frequency of array elements Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // Traverse the array for(int i = 0; i < N; i++) { // Update frequency of // current element if (!map.containsKey(arr[i])) map.put(arr[i], 1); else map.replace(arr[i], map.get(arr[i]) + 1); } // Stores sum of odd and even // frequent elements int sum_odd = 0, sum_even = 0; // Traverse the map Set<Map.Entry<Integer, Integer>> hmap = map.entrySet(); for(Map.Entry<Integer, Integer> data:hmap) { int key = data.getKey(); int val = data.getValue(); // If frequency is odd if (val % 2 != 0) // Add sum of all occurrences of // current element to sum_odd sum_odd += (key) * (val); // If frequency is even if (val % 2 == 0) // Add sum of all occurrences of // current element to sum_even sum_even += (key) * (val); } // Calculate difference // between their sum int diff = sum_even - sum_odd; // Return diff return diff; } // Driver Code public static void main(String args[]) { int arr[] = { 1, 5, 5, 2, 4, 3, 3 }; int N = arr.length; System.out.println(findSum(arr, N)); }}// This code is contributed by jyoti369 |
Python3
# Python3 program to find absolute difference # between the sum of all odd frequent and # even frequent elements in an array# Function to find the sum of all even # and odd frequent elements in an array def findSum(arr, N): # Stores the frequency of array elements mp = {} # Traverse the array for i in range(0, N): # Update frequency of # current element if arr[i] in mp: mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Stores sum of odd and even # frequent elements sum_odd, sum_even = 0, 0 # Traverse the map for itr in mp: # If frequency is odd if (mp[itr] % 2 != 0): # Add sum of all occurrences of # current element to sum_odd sum_odd += (itr) * (mp[itr]) # If frequency is even if (mp[itr] % 2 == 0): # Add sum of all occurrences of # current element to sum_even sum_even += (itr) * (mp[itr]) # Calculate difference # between their sum diff = sum_even - sum_odd # Return diff return diff# Driver codearr = [ 1, 5, 5, 2, 4, 3, 3 ] N = len(arr)print(findSum(arr, N))# This code is contributed by divyeshrabadiya07 |
C#
// C# program to find absolute difference // between the sum of all odd frequent and // even frequent elements in an array using System;using System.Collections.Generic; class GFG { // Function to find the sum of all even // and odd frequent elements in an array static int findSum(int[] arr, int N) { // Stores the frequency of array elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < N; i++) { // Update frequency of // current element if(mp.ContainsKey(arr[i])) { mp[arr[i]]++; } else{ mp[arr[i]] = 1; } } // Stores sum of odd and even // frequent elements int sum_odd = 0, sum_even = 0; // Traverse the map foreach(KeyValuePair<int, int> itr in mp) { // If frequency is odd if (itr.Value % 2 != 0) // Add sum of all occurrences of // current element to sum_odd sum_odd += (itr.Key) * (itr.Value); // If frequency is even if (itr.Value % 2 == 0) // Add sum of all occurrences of // current element to sum_even sum_even += (itr.Key) * (itr.Value); } // Calculate difference // between their sum int diff = sum_even - sum_odd; // Return diff return diff; } // Driver code static void Main() { int[] arr = { 1, 5, 5, 2, 4, 3, 3 }; int N = arr.Length; Console.Write(findSum(arr, N)); }}// This code is contributed by divyesh072019. |
Javascript
<script>// JavaScript program to find absolute difference // between the sum of all odd frequent and // even frequent elements in an array // Function to find the sum of all even // and odd frequent elements in an array function findSum(arr, N) { // Stores the frequency of array elements var mp = {}; for(let i =0; i<N;i++) mp[arr[i]] = 0; // Traverse the array for (let i = 0; i < N; i++) { // Update frequency of // current element mp[arr[i]]++; } // Stores sum of odd and even // frequent elements var sum_odd = 0, sum_even = 0; // Traverse the map for (let itr in mp) { // If frequency is odd if (mp[itr] % 2 != 0) { // Add sum of all occurrences of // current element to sum_odd sum_odd += (itr) * (mp[itr]); } // If frequency is even if (mp[itr] % 2 == 0) { // Add sum of all occurrences of // current element to sum_even sum_even += (itr) * (mp[itr]); } } // Calculate difference // between their sum var diff = sum_even - sum_odd; // Return diff return diff; } // Driver Code var arr = new Array( 1, 5, 5, 2, 4, 3, 3 ); var N = arr.length; console.log( findSum(arr, N) ); // This code is contributed by ukasp. </script> |
Output
9
Time Complexity: O(N)
Auxiliary Space: O(N)
Approach without using extra space:
- We can just sort the array
- After sorting all same time off elements will be adjacent to each other
- We can count the frequency of a element and add the element according to the odd or even frequency
Implementation:-
C++
// C++ program to find absolute difference // between the sum of all odd frequent and // even frequent elements in an array #include <bits/stdc++.h> using namespace std; // Function to find the sum of all even // and odd frequent elements in an array int findSum(int arr[], int N) { //sorting the array sort(arr,arr+N); //taking the first element as initial element //and frequency as 1 int freq=1,element=arr[0]; //to store sum of odd time and //even time present elements int odd_sum=0,even_sum=0; //traversing the array from second element for(int i=1;i<N;i++) { //if another element found if(arr[i]!=element) { //if previous element frequency was odd if(freq%2){ odd_sum+=freq*element; } else{ even_sum+=freq*element; } //setting frequency of new element as 1 freq=1; element=arr[i]; } else freq++; } //if last element frequency was odd if(freq%2){ odd_sum+=freq*element; } else{ even_sum+=freq*element; } return abs(odd_sum-even_sum);} // Driver Code int main() { int arr[] = { 1, 5, 5, 2, 4, 3, 3 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findSum(arr, N); return 0; }//This code contributed by shubhamrajput6156 |
Java
import java.util.*;public class Main { // Function to find the sum of all even // and odd frequent elements in an array static int findSum(int[] arr, int N) { //sorting the array Arrays.sort(arr); //taking the first element as initial element //and frequency as 1 int freq=1,element=arr[0]; //to store sum of odd time and //even time present elements int odd_sum=0,even_sum=0; //traversing the array from second element for(int i=1;i<N;i++) { //if another element found if(arr[i]!=element) { //if previous element frequency was odd if(freq%2 == 1){ odd_sum+=freq*element; } else{ even_sum+=freq*element; } //setting frequency of new element as 1 freq=1; element=arr[i]; } else freq++; } //if last element frequency was odd if(freq%2 == 1){ odd_sum+=freq*element; } else{ even_sum+=freq*element; } return Math.abs(odd_sum-even_sum); } // Driver Code public static void main(String[] args) { int[] arr = { 1, 5, 5, 2, 4, 3, 3 }; int N = arr.length; System.out.println(findSum(arr, N)); } } |
Python3
# python program to find absolute difference # between the sum of all odd frequent and # even frequent elements in an array# Function to find the sum of all even# and odd frequent elements in an arraydef find_sum(arr, N): # Sorting the array arr.sort() # Taking the first element as initial element # and frequency as 1 freq = 1 element = arr[0] # To store sum of odd time and # even time present elements odd_sum = 0 even_sum = 0 # Traversing the array from second element for i in range(1, N): # If another element found if arr[i] != element: # If previous element frequency was odd if freq % 2: odd_sum += freq * element else: even_sum += freq * element # Setting frequency of new element as 1 freq = 1 element = arr[i] else: freq += 1 # If last element frequency was odd if freq % 2: odd_sum += freq * element else: even_sum += freq * element return abs(odd_sum - even_sum)# Driver Codeif __name__ == "__main__": arr = [1, 5, 5, 2, 4, 3, 3] N = len(arr) print(find_sum(arr,N)) |
C#
using System;public class Program{ // Function to find the sum of all even // and odd frequent elements in an array public static int FindSum(int[] arr, int N) { // sorting the array Array.Sort(arr); // taking the first element as initial element // and frequency as 1 int freq = 1, element = arr[0]; // to store sum of odd time and // even time present elements int odd_sum = 0, even_sum = 0; // traversing the array from second element for (int i = 1; i < N; i++) { // if another element found if (arr[i] != element) { // if previous element frequency was odd if (freq % 2 != 0) { odd_sum += freq * element; } else { even_sum += freq * element; } // setting frequency of new element as 1 freq = 1; element = arr[i]; } else { freq++; } } // if last element frequency was odd if (freq % 2 != 0) { odd_sum += freq * element; } else { even_sum += freq * element; } return Math.Abs(odd_sum - even_sum); } // Driver Code public static void Main() { int[] arr = { 1, 5, 5, 2, 4, 3, 3 }; int N = arr.Length; Console.WriteLine(FindSum(arr, N)); }} |
Javascript
//Javascript program to find absolute difference // between the sum of all odd frequent and // even frequent elements in an array// Function to find the sum of all even// and odd frequent elements in an arrayfunction find_sum(arr, N) { // Sorting the array arr.sort(); // Taking the first element as initial element // and frequency as 1 let freq = 1; let element = arr[0]; // To store sum of odd time and // even time present elements let odd_sum = 0; let even_sum = 0; // Traversing the array from second element for (let i = 1; i < N; i++) { // If another element found if (arr[i] !== element) { // If previous element frequency was odd if (freq % 2) { odd_sum += freq * element; } else { even_sum += freq * element; } // Setting frequency of new element as 1 freq = 1; element = arr[i]; } else { freq++; } } // If last element frequency was odd if (freq % 2) { odd_sum += freq * element; } else { even_sum += freq * element; } return Math.abs(odd_sum - even_sum);}// Driver Code let arr = [1, 5, 5, 2, 4, 3, 3]; let N = arr.length; console.log(find_sum(arr,N)); |
Output
9
Time Complexity:- O(NlogN)
Auxiliary Space:- O(1)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
