Check if the sum of K least and most frequent array elements are equal or not
Given an array arr[] consisting of N integers, the task is to check if the sum of K most frequent array elements and the sum of K least frequent array elements in the array arr[] are equal or not. If found to be true, then print Yes. Otherwise, print No.
Examples:
Input: arr[] = { 3, 2, 1, 2, 3, 3, 4 }, K=2
Output: Yes
Explanation:
The frequency of each element is given by:
- 3, the frequency is 3.
- 2, the frequency is 2.
- 1, the frequency is 1.
- 4, the frequency is 1.
The sum of K(= 2) most frequent elements is 3 + 2 = 5 and the sum of K(= 2) least frequent elements is 1 + 4 =5. Hence, print Yes.
Input: arr[] = {1, 2, 4, 1, 1, 3, 2, 4, 2, 5, 3}, K = 3
Output: No
Approach: The given problem can be solved by finding the K most frequent elements using hashing with frequency indexing and, according to the frequency array find the sum of K most frequent elements is equal to the sum of K Least frequent elements in the array arr[]. Follow the steps below to solve the problem:
- Initialize an unordered map, say M to count the frequency of each array element.
- Iterate over a range [0, N] and store the frequency of each array element in the unordered map M.
- Initialize a 2-D vector freq of size N + 1 to store the elements at a given frequency in the map M.
- Iterate over a range [0, N] and perform the following steps:
- Initialize a variable f as the frequency of arr[i], i.e., M[arr[i]].
- If f is not equal to -1, then push the element arr[i] into the vector freq for the frequency f and set the value of m[arr[i]] to -1.
- Initialize the variable count as 0 to keep track of the K most frequent elements and the K Least frequent array elements.
- Initialize the variable kleastfreqelem as 0 to store the sum of K least frequent array elements.
- Iterate over a range [0, N] using the variable i and perform the following steps:
- Iterate over a range [0, freq[i]] and perform the following steps:
- Add the value of freq[i][j] to the variable kleastfreqelem and increase the value of count by 1.
- If the count is equal to K, then, break out of the loop.
- If count is equal to K, then break the loop.
- Iterate over a range [0, freq[i]] and perform the following steps:
- Set the value of the count to 0.
- Initialize the variable kmostfreqelem as 0 to store the sum of the K Least frequent elements of the array arr[].
- Iterate over a range [N-1, 0] using the variable i and perform the following steps:
- Iterate over a range [0, freq[i]] and perform the following steps:
- Add the value of freq[i][j] to the variable kmostfreqelem and increase the value of count by 1.
- If the count is equal to K, then break out of the loop.
- If the count is equal to K, then break out of the loop.
- Iterate over a range [0, freq[i]] and perform the following steps:
- If the value of kmostfreqelem is equal to kleastelem, then print Yes. Otherwise, print No.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to compare the sum of K // most and least occurrences string checkSum( int arr[], int n, int k) { // Stores frequency of array element unordered_map< int , int > m; for ( int i = 0; i < n; i++) m[arr[i]]++; // Stores the frequencies as indexes // and putelements with the frequency // in a vector vector< int > freq[n + 1]; for ( int i = 0; i < n; i++) { // Find the frequency int f = m[arr[i]]; if (f != -1) { // Insert in the vector freq[f].push_back(arr[i]); m[arr[i]] = -1; } } // Stores the count of elements int count = 0; int kleastfreqsum = 0; // Traverse the frequency array for ( int i = 0; i <= n; i++) { // Find the kleastfreqsum for ( int x : freq[i]) { kleastfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Reinitialize the count to zero count = 0; int kmostfreqsum = 0; // Traverse the frequency for ( int i = n; i >= 0; i--) { // Find the kmostfreqsum for ( int x : freq[i]) { kmostfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Comparing the sum if (kleastfreqsum == kmostfreqsum) return "Yes" ; // Otherwise, return No return "No" ; } // Driver Code int main() { int arr[] = { 3, 2, 1, 2, 3, 3, 4 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 2; cout << checkSum(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to compare the sum of K // most and least occurrences static String checkSum( int arr[], int n, int k) { // Stores frequency of array element HashMap<Integer,Integer> m = new HashMap<Integer,Integer>(); for ( int i = 0 ; i < n; i++) if (m.containsKey(arr[i])){ m.put(arr[i], m.get(arr[i])+ 1 ); } else { m.put(arr[i], 1 ); } // Stores the frequencies as indexes // and putelements with the frequency // in a vector Vector<Integer> []freq = new Vector[n + 1 ]; for ( int i = 0 ; i < freq.length; i++) freq[i] = new Vector<Integer>(); for ( int i = 0 ; i < n; i++) { // Find the frequency int f = m.get(arr[i]); if (f != - 1 ) { // Insert in the vector freq[f].add(arr[i]); m.put(arr[i], - 1 ); } } // Stores the count of elements int count = 0 ; int kleastfreqsum = 0 ; // Traverse the frequency array for ( int i = 0 ; i <= n; i++) { // Find the kleastfreqsum for ( int x : freq[i]) { kleastfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Reinitialize the count to zero count = 0 ; int kmostfreqsum = 0 ; // Traverse the frequency for ( int i = n; i >= 0 ; i--) { // Find the kmostfreqsum for ( int x : freq[i]) { kmostfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Comparing the sum if (kleastfreqsum == kmostfreqsum) return "Yes" ; // Otherwise, return No return "No" ; } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 2 , 1 , 2 , 3 , 3 , 4 }; int N = arr.length; int K = 2 ; System.out.print(checkSum(arr, N, K)); } } // This code is contributed by 29AjayKumar. |
Python3
# Python3 program for the above approach # Function to compare the sum of K # most and least occurrences def checkSum(arr, n, k): # Stores frequency of array element m = {} for i in range (n): if arr[i] in m: m[arr[i]] + = 1 else : m[arr[i]] = 1 # Stores the frequencies as indexes # and putelements with the frequency # in a vector freq = [[] for i in range (n + 1 )] for i in range (n): # Find the frequency f = m[arr[i]] if (f ! = - 1 ): # Insert in the vector freq[f].append(arr[i]) m[arr[i]] = - 1 # Stores the count of elements count = 0 kleastfreqsum = 0 # Traverse the frequency array for i in range (n + 1 ): # Find the kleastfreqsum for x in freq[i]: kleastfreqsum + = x count + = 1 if (count = = k): break # If the count is K, break if (count = = k): break # Reinitialize the count to zero count = 0 kmostfreqsum = 0 # Traverse the frequency i = n while (i > = 0 ): # Find the kmostfreqsum for x in freq[i]: kmostfreqsum + = x count + = 1 if (count = = k): break i - = 1 # If the count is K, break if (count = = k): break # Comparing the sum if (kleastfreqsum = = kmostfreqsum): return "Yes" # Otherwise, return No return "No" # Driver Code if __name__ = = '__main__' : arr = [ 3 , 2 , 1 , 2 , 3 , 3 , 4 ] N = len (arr) K = 2 print (checkSum(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to compare the sum of K // most and least occurrences static String checkSum( int [] arr, int n, int k) { // Stores frequency of array element Dictionary< int , int > m = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) if (m.ContainsKey(arr[i])) { m[arr[i]] = m[arr[i]] + 1; } else { m.Add(arr[i], 1); } // Stores the frequencies as indexes // and putelements with the frequency // in a vector List< int >[] freq = new List< int >[ n + 1 ]; for ( int i = 0; i < freq.Length; i++) freq[i] = new List< int >(); for ( int i = 0; i < n; i++) { // Find the frequency int f = m[arr[i]]; if (f != -1) { // Insert in the vector freq[f].Add(arr[i]); if (m.ContainsKey(arr[i])) { m[arr[i]] = -1; } else { m.Add(arr[i], -1); } } } // Stores the count of elements int count = 0; int kleastfreqsum = 0; // Traverse the frequency array for ( int i = 0; i <= n; i++) { // Find the kleastfreqsum foreach ( int x in freq[i]) { kleastfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Reinitialize the count to zero count = 0; int kmostfreqsum = 0; // Traverse the frequency for ( int i = n; i >= 0; i--) { // Find the kmostfreqsum foreach ( int x in freq[i]) { kmostfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Comparing the sum if (kleastfreqsum == kmostfreqsum) return "Yes" ; // Otherwise, return No return "No" ; } // Driver Code public static void Main(String[] args) { int [] arr = { 3, 2, 1, 2, 3, 3, 4 }; int N = arr.Length; int K = 2; Console.Write(checkSum(arr, N, K)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript program for the above approach // Function to compare the sum of K // most and least occurrences function checkSum(arr, n, k) { // Stores frequency of array element let m = new Map(); for (let i = 0; i < n; i++) { if (m.has(arr[i])) { m.set(m.get(arr[i]), m.get(arr[i]) + 1) } else { m.set(arr[i], 1); } } // Stores the frequencies as indexes // and putelements with the frequency // in a vector let freq = new Array(n + 1); for (let i = 0; i < n; i++) { // Find the frequency let f = m.get(arr[i]); if (f != -1) { // Insert in the vector freq[f] = new Array(); freq[f].push(arr[i]); m.set(arr[i], -1); } } // Stores the count of elements let count = 0; let kleastfreqsum = 0; // Traverse the frequency array for (let i = 0; i <= n; i++) { // Find the kleastfreqsum for (let x in freq[i]) { kleastfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Reinitialize the count to zero count = 0; let kmostfreqsum = 0; // Traverse the frequency for (let i = n; i >= 0; i--) { // Find the kmostfreqsum for (let x in freq[i]) { kmostfreqsum += x; count++; if (count == k) break ; } // If the count is K, break if (count == k) break ; } // Comparing the sum if (kleastfreqsum == kmostfreqsum) return "Yes" ; // Otherwise, return No return "No" ; } // Driver Code let arr = [3, 2, 1, 2, 3, 3, 4]; let N = arr.length; let K = 2; document.write(checkSum(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)