Given an integer array arr[], the task is to find an element in the array whose frequency is equal to the sum of frequencies of other elements of the array.
Examples:
Input: arr[] = {1, 2, 2, 3, 3, 3}
Output: 3
Explanation:
Frequencies of elements of the array –
Frequency(3) = 3
Frequency(2) = 2
Frequency(1) = 1
Here, the frequency of element 3 is equal to the
the sum of frequencies of other elements of the array.Input: arr[] = {1, 2, 3}
Output: -1
Explanation:
In the above-given array, there is no such
element whose frequency is equal to the sum of
frequencies of other elements of the array.
Approach: The key observation in the problem is if the length of the array is odd, then there will be no such element, whereas, in the case of an even length array, calculate the frequency of each element of the array and then finally, check for any element of the array that has a frequency equal to the half-length of the array.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // element whose frequency is equal // to the sum of frequencies of // other elements of the array #include <bits/stdc++.h> using namespace std; // Function to check that any element // have frequency equal to the sum of // frequency of other elements of the array bool isFrequencyEqual( int arr[], int len) { // Check that if the array length // is odd, Then no solution possible if (len % 2 == 1){ cout << "No Such Element" ; return false ; } // Hash-map to store the frequency // of elements of array map< int , int > freq; // Loop to find the frequency // of elements of array for ( int i = 0; i < len; i++) freq[arr[i]]++; // Loop to check if any element // of the array have frequency // equal to the half length for ( int i = 0; i < len; i++){ if (freq[arr[i]] == len / 2){ cout << arr[i] << endl; return true ; } } cout << "No such element" ; return false ; } // Driver Code int main() { int arr[6] = { 1, 2, 2, 3, 3, 3 }; int n = 6; // Function Call isFrequencyEqual(arr, n); return 0; } |
Java
// Java implementation to find the // element whose frequency is equal // to the sum of frequencies of // other elements of the array import java.util.*; class GFG{ // Function to check that any element // have frequency equal to the sum of // frequency of other elements of the array static boolean isFrequencyEqual( int arr[], int len) { // Check that if the array length // is odd, Then no solution possible if (len % 2 == 1 ){ System.out.print( "No Such Element" ); return false ; } // Hash-map to store the frequency // of elements of array HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>(); // Loop to find the frequency // of elements of array for ( int i = 0 ; i < len; i++) if (freq.containsKey(arr[i])){ freq.put(arr[i], freq.get(arr[i])+ 1 ); } else { freq.put(arr[i], 1 ); } // Loop to check if any element // of the array have frequency // equal to the half length for ( int i = 0 ; i < len; i++){ if (freq.containsKey(arr[i]) && freq.get(arr[i]) == len / 2 ){ System.out.print(arr[i] + "\n" ); return true ; } } System.out.print( "No such element" ); return false ; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 2 , 3 , 3 , 3 }; int n = 6 ; // Function Call isFrequencyEqual(arr, n); } } // This code is contributed by Rajput-Ji |
C#
// C# implementation to find the // element whose frequency is equal // to the sum of frequencies of // other elements of the array using System; using System.Collections.Generic; class GFG{ // Function to check that any element // have frequency equal to the sum of // frequency of other elements of the array static bool isFrequencyEqual( int []arr, int len) { // Check that if the array length // is odd, Then no solution possible if (len % 2 == 1){ Console.Write( "No Such Element" ); return false ; } // Hash-map to store the frequency // of elements of array Dictionary< int , int > freq = new Dictionary< int , int >(); // Loop to find the frequency // of elements of array for ( int i = 0; i < len; i++) if (freq.ContainsKey(arr[i])){ freq[arr[i]] = freq[arr[i]]+1; } else { freq.Add(arr[i], 1); } // Loop to check if any element // of the array have frequency // equal to the half length for ( int i = 0; i < len; i++){ if (freq.ContainsKey(arr[i]) && freq[arr[i]] == len / 2){ Console.Write(arr[i] + "\n" ); return true ; } } Console.Write( "No such element" ); return false ; } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 2, 3, 3, 3 }; int n = 6; // Function Call isFrequencyEqual(arr, n); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation to find the # element whose frequency is equal # to the sum of frequencies of # other elements of the array # Function to check that any element # have frequency equal to the sum of # frequency of other elements of the array def isFrequencyEqual(arr, length) : # Check that if the array length # is odd, Then no solution possible if (length % 2 = = 1 ) : print ( "No Such Element" ); return False ; # Hash-map to store the frequency # of elements of array freq = dict .fromkeys(arr, 0 ); # Loop to find the frequency # of elements of array for i in range (length) : freq[arr[i]] + = 1 ; # Loop to check if any element # of the array have frequency # equal to the half length for i in range (length) : if (freq[arr[i]] = = length / 2 ) : print (arr[i]); return True ; print ( "No such element" ,end = ""); return False ; # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 2 , 3 , 3 , 3 ]; n = 6 ; # Function Call isFrequencyEqual(arr, n); # This code is contributed by Yash_R |
Javascript
<script> // Javascript program // Function to check that any element // have frequency equal to the sum of // frequency of other elements of the array function isFrequencyEqual(arr, len) { // Check that if the array length // is odd, Then no solution possible if (len % 2 == 1){ document.write( "No Such Element" ); return false ; } // Hash-map to store the frequency // of elements of array var freq = {}; for ( var i = 0; i < len; i++) freq[arr[i]] = 0; // Loop to find the frequency // of elements of array for ( var i = 0; i < len; i++) freq[arr[i]]++; // Loop to check if any element // of the array have frequency // equal to the half length for ( var i = 0; i < len; i++){ if (freq[arr[i]] == len / 2){ document.write(arr[i]); return true ; } } document.write( "No such element" ); return false ; } var arr = [ 1, 2, 2, 3, 3, 3]; var n = 6; isFrequencyEqual(arr, n); </script> |
3
Time Complexity: O(NLogN)
Space Complexity: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!