Given a NxM matrix of integers containing duplicate elements. The task is to find the sum of all minimum occurring elements in the given matrix. That is the sum of all such elements whose frequency is even in the matrix.
Examples:
Input : mat[] = {{1, 1, 2},
{2, 3, 3},
{4, 5, 3}}
Output : 9
The min occurring elements are 4, 5 and they
occurs only 1 time.
Therefore, sum = 4+5 = 9
Input : mat[] = {{10, 20},
{40, 40}}
Output : 30
Approach:
- Traverse the matrix and use a map in C++ to store the frequency of elements of the matrix such that the key of map is the matrix element and value is its frequency in the matrix.
- Then traverse the map to find the minimum frequency.
- Finally, traverse the map to find the frequency of elements and check if it matches with the minimum frequency obtained in previous step, if yes, then add this element its frequency times to sum.
Below is the implementation of the above approach:
C++
// C++ program to find sum of all min// frequency elements in a Matrix#include <bits/stdc++.h>using namespace std;#define N 3 // Rows#define M 3 // Columns// Function to find sum of all min// frequency elements in a Matrixint sumMinOccurring(int arr[N][M]){ // Store frequencies of elements // in matrix map<int, int> mp; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { mp[arr[i][j]]++; } } // Find minimum frequency int sum = 0; int minFreq = INT_MAX; for (auto itr = mp.begin(); itr != mp.end(); itr++) { if (itr->second < minFreq) minFreq = itr->second; } // Sum of minimum frequency elements for (auto itr = mp.begin(); itr != mp.end(); itr++) { if (itr->second == minFreq) { sum += (itr->first) * (itr->second); } } return sum;}// Driver Codeint main(){ int mat[N][M] = { { 1, 2, 3 }, { 1, 3, 2 }, { 1, 5, 6 } }; cout << sumMinOccurring(mat) << endl; return 0;} |
Java
// Java program to find sum of all min // frequency elements in a Matrix import java.util.HashMap;import java.util.Iterator;class GFG { static int N = 3; // Rows static int M = 3; // Columns // Function to find sum of all min // frequency elements in a Matrix public static int sumMinOccuring(int[][] arr) { // Store frequencies of elements // in matrix HashMap<Integer, Integer> mp = new HashMap<>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mp.containsKey(arr[i][j])) { int x = mp.get(arr[i][j]); mp.put(arr[i][j], x + 1); } else mp.put(arr[i][j], 1); } } // Find minimum frequency int sum = 0; int minFreq = Integer.MAX_VALUE; for (HashMap.Entry<Integer, Integer> entry : mp.entrySet()) { if (entry.getValue() < minFreq) minFreq = entry.getValue(); } // Sum of minimum frequency elements for (HashMap.Entry<Integer, Integer> entry : mp.entrySet()) { if (entry.getValue() == minFreq) sum += entry.getKey() * entry.getValue(); } return sum; } // Driver code public static void main(String[] args) { int[][] mat = { { 1, 2, 3 }, { 1, 3, 2 }, { 1, 5, 6 } }; System.out.println(sumMinOccuring(mat)); }}// This code is contributed by// sanjeev2552 |
Python3
# Python3 program to find sum of all min # frequency elements in a Matrix import sysimport math# Store frequencies of elements # in matrixdef sumMinOccurring(mat): n,m=len(mat),len(mat[0]) _map={} for i in range(n): for j in range(m): d=mat[i][j] if d in _map: _map[d]=_map.get(d)+1 else: _map[d]=1 # Find minimum frequency _sum,minFreq=0,sys.maxsize for i in _map: minFreq=min(minFreq,_map.get(i)) # Sum of minimum frequency elements for i in range(n): for j in range(m): if _map.get(mat[i][j])==minFreq: _sum+=mat[i][j] return _sum # Driver Codeif __name__=='__main__': mat=[[1,2,3],[1,3,2],[1,5,6]] print(sumMinOccurring(mat))# This code is Contributed by Vikash Kumar 37 |
C#
// C# program to find sum of all min // frequency elements in a Matrix using System; using System.Collections.Generic;class GFG { static int N = 3; // Rows static int M = 3; // Columns // Function to find sum of all min // frequency elements in a Matrix public static int sumMinOccuring(int[,] arr) { // Store frequencies of elements // in matrix Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (mp.ContainsKey(arr[i, j])) { int x = mp[arr[i, j]]; mp[arr[i, j]] = x + 1; } else mp[arr[i, j]] = 1; } } // Find minimum frequency int sum = 0; int minFreq = 10000009; foreach(KeyValuePair<int, int> ele1 in mp) { if(ele1.Value < minFreq) minFreq = ele1.Value; } // Sum of minimum frequency elements foreach(KeyValuePair<int, int> ele1 in mp) { if (ele1.Value == minFreq) sum += ele1.Key * ele1.Value; } return sum; } // Driver code public static void Main() { int[,] mat = new int[3, 3] {{ 1, 2, 3 }, { 1, 3, 2 }, { 1, 5, 6 }}; Console.Write(sumMinOccuring(mat)); }}// This code is contributed by// Mohit kumar |
Javascript
<script>// JavaScript program to find sum of all min // frequency elements in a Matrix let N = 3; // Rowslet M = 3; // Columns// Function to find sum of all min // frequency elements in a Matrixfunction sumMinOccuring(arr){ // Store frequencies of elements // in matrix let mp = new Map(); for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (mp.has(arr[i][j])) { let x = mp.get(arr[i][j]); mp.set(arr[i][j], x + 1); } else mp.set(arr[i][j], 1); } } // Find minimum frequency let sum = 0; let minFreq = Number.MAX_VALUE; for (let [key, value] of mp.entries()) { if (value < minFreq) minFreq = value; } // Sum of minimum frequency elements for (let [key, value] of mp.entries()) { if (value == minFreq) sum += key * value; } return sum;}// Driver codelet mat=[[1,2,3],[1,3,2],[1,5,6]];document.write(sumMinOccuring(mat));// This code is contributed by patel2127</script> |
Output
11
Complexity Analysis:
- Time Complexity: O(M x N)
- Auxiliary Space : O(M x N)
Share your thoughts in the comments
