Max count of items that can be removed from the Array without changing the mode
Given an array arr[] of N integers, the goal is to find the maximum count of items that can be removed from the array without changing the mode. You can remove any number of occurrences of items of the same value let’s say K at one step. Now, for removing the next value i.e., different from K, the array comes back to its Initial state. If two or more elements are competing for mode, then consider the one having the highest value.
Examples:
Input: arr[] = {1, 4, 1, 2, 7, 1, 2, 5, 3, 6}
Output: 7
Explanation: Count of 1 = 3, 2 = 2, {3, 4, 5, 6, 7} all having count = 1
Mode = 1 and its count = 3,
If we remove 2, 3, 4, 5, 6, 7 then the mode does not change.
But if we remove any item of 1, then count of 1 = count of 2, as 2 > 1, so, the mode changes if we remove 1. So, Count = 7.Input: arr[] = {1, 2, 2, 2, 1}
Output: 3
Explanation: Count of 1 = 2 and 2 = 3.
Mode = 2 and its count = 3,
If we remove 1, 1 then the mode does not change.
If we remove one count of 2 then also, mode does not change, as count of 1 = count of 2, but 2 > 1, so, there is no effect on mode. So, Count = 3.
Approach: To solve the problem follow the below idea:
We can solve this problem using hashing. We will try to find the maximum element from the array first and store it in variable. Then we will create hash map to store the count of each element of array. And then we will try to find the first largest mode and then the second largest mode to calculate the result.
Follow the steps to solve the problem:
- Initialize Hash map count.
- Next, store count of each element of input array in the count map.
- Find first largest Mode and second largest Mode and store it in Mode1 and Mode2 respectively.
- Store count of Mode1 in k1 and count of Mode2 in k2.
- If k1 is equal to k2 then return N-k1.
- If Mode1 is greater than Mode2 then return N-k2.
- Else return N-k2-1.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Function that count the items int printMode( int a[], int n) { // Hash map to store the count of // the elements unordered_map< int , int > count; // Store count of each element // of input array for ( int i = 0; i < n; i++) count[a[i]]++; // First Largest Mode int Mode1; int k1 = INT_MIN; for ( int i = 0; i < n; i++) { if (count[a[i]] > k1 || ((count[a[i]] == k1) && (a[i] > Mode1))) { k1 = count[a[i]]; Mode1 = a[i]; } } // Second Largest Mode int Mode2; int k2 = INT_MIN; for ( int i = 0; i < n; i++) { if ((a[i] != Mode1) && (count[a[i]] > k2 || ((count[a[i]] == k2) && (a[i] > Mode2)))) { k2 = count[a[i]]; Mode2 = a[i]; } } // Return count if (k1 == k2) return n - k1; if (Mode1 > Mode2) return n - k2; return n - k2 - 1; } // Driver Code int main() { int arr[] = { 1, 4, 1, 2, 7, 1, 2, 5, 3, 6 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << printMode(arr, N); return 0; } |
Java
// Java Program for the above approach import java.util.*; class GFG { // Function that count the items static int printMode( int [] a, int n) { // Hash map to store the count of // the elements Map<Integer, Integer> count = new HashMap<>(); // Store count of each element // of input array for ( int i = 0 ; i < n; i++) { count.put(a[i], count.getOrDefault(a[i], 0 ) + 1 ); } // First Largest Mode int Mode1 = 0 ; int k1 = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { if (count.get(a[i]) > k1 || ((count.get(a[i]) == k1) && (a[i] > Mode1))) { k1 = count.get(a[i]); Mode1 = a[i]; } } // Second Largest Mode int Mode2 = 0 ; int k2 = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { if ((a[i] != Mode1) && (count.get(a[i]) > k2 || ((count.get(a[i]) == k2) && (a[i] > Mode2)))) { k2 = count.get(a[i]); Mode2 = a[i]; } } // Return count if (k1 == k2) return n - k1; if (Mode1 > Mode2) return n - k2; return n - k2 - 1 ; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 4 , 1 , 2 , 7 , 1 , 2 , 5 , 3 , 6 }; int N = arr.length; // Function Call System.out.println(printMode(arr, N)); } } // This code is contributed by ragul21 |
Python
# Python program for the above approach # Function that counts the items def printMode(arr, n): # Hash map to store the count of # the elements count = {} # Store count of each element # of the input array for i in range (n): count[arr[i]] = count.get(arr[i], 0 ) + 1 # First Largest Mode Mode1 = None k1 = float ( '-inf' ) for i in range (n): if count[arr[i]] > k1 or ((count[arr[i]] = = k1) and (arr[i] > Mode1)): k1 = count[arr[i]] Mode1 = arr[i] # Second Largest Mode Mode2 = None k2 = float ( '-inf' ) for i in range (n): if (arr[i] ! = Mode1) and (count[arr[i]] > k2 or ((count[arr[i]] = = k2) and (arr[i] > Mode2))): k2 = count[arr[i]] Mode2 = arr[i] # Return count if k1 = = k2: return n - k1 if Mode1 > Mode2: return n - k2 return n - k2 - 1 # Driver Code arr = [ 1 , 4 , 1 , 2 , 7 , 1 , 2 , 5 , 3 , 6 ] N = len (arr) # Function Call print (printMode(arr, N)) # this code is contributed by uttamdp_10 |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { static int PrintMode( int [] arr, int n) { Dictionary< int , int > count = new Dictionary< int , int >(); // Store count of each element // of the input array for ( int i = 0; i < n; i++) { if (count.ContainsKey(arr[i])) { count[arr[i]]++; } else { count[arr[i]] = 1; } } // First Largest Mode int mode1 = 0; // Initialize mode1 int k1 = int .MinValue; for ( int i = 0; i < n; i++) { if (count[arr[i]] > k1 || ((count[arr[i]] == k1) && (arr[i] > mode1))) { k1 = count[arr[i]]; mode1 = arr[i]; } } // Second Largest Mode int mode2 = 0; // Initialize mode2 int k2 = int .MinValue; for ( int i = 0; i < n; i++) { if ((arr[i] != mode1) && (count[arr[i]] > k2 || ((count[arr[i]] == k2) && (arr[i] > mode2)))) { k2 = count[arr[i]]; mode2 = arr[i]; } } // Return count if (k1 == k2) return n - k1; if (mode1 > mode2) return n - k2; return n - k2 - 1; } // Driver Code static void Main() { int [] arr = { 1, 4, 1, 2, 7, 1, 2, 5, 3, 6 }; int N = arr.Length; // Function Call Console.WriteLine(PrintMode(arr, N)); } } |
Javascript
function printMode(arr) { // Hash map to store the count of the elements let count = new Map(); // Store count of each element of input array for (let i = 0; i < arr.length; i++) { if (!count.has(arr[i])) { count.set(arr[i], 1); } else { count.set(arr[i], count.get(arr[i]) + 1); } } // First Largest Mode let mode1; let k1 = -Infinity; for (let i = 0; i < arr.length; i++) { if (count.get(arr[i]) > k1 || (count.get(arr[i]) === k1 && arr[i] > mode1)) { k1 = count.get(arr[i]); mode1 = arr[i]; } } // Second Largest Mode let mode2; let k2 = -Infinity; for (let i = 0; i < arr.length; i++) { if (arr[i] !== mode1 && (count.get(arr[i]) > k2 || (count.get(arr[i]) === k2 && arr[i] > mode2))) { k2 = count.get(arr[i]); mode2 = arr[i]; } } // Return count if (k1 === k2) { return arr.length - k1; } if (mode1 > mode2) { return arr.length - k2; } return arr.length - k2 - 1; } // Driver Code let arr = [1, 4, 1, 2, 7, 1, 2, 5, 3, 6]; console.log(printMode(arr)); |
7
Time Complexity: O(N)
Auxiliary Space: O(N)