# Minimize deletions in Array by deleting all occurrences of any number such that array size is reduced to at least half

Given an array **arr[]** of positive integers, the task is to **select** an element from the array and **delete** all its occurrences, such that the number of elements selected are **minimum** and the array size becomes **atleast half** of its original size.**Note: **Size of the given array is always even.

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {2, 2, 2, 2, 4, 4, 6, 7, 7, 3, 3, 3}Output:2Explanation: First we select 2 and delete all its occurences after that arr[] becomes – {4, 4, 6, 7, 7, 3, 3, 3} with size = 8. As the size is still greater than half, we select 3 and delete all its occurences, after that arr[] becomes – {4, 4, 6, 7, 7} with size = 5.

Input:arr[] = {3, 3, 3, 3, 3}Output:1Explanation: select 3 and remove all its occurences.

**Approach: **The task can be easily achieved by removing the elements with maximum frequency, as soon as the array size becomes at least half of the actual size, we return the number of unique elements deleted till now.

Follow the steps to solve the problem:

- Use Hash-map to store frequency of the elements in array present.
- Store the frequencies in a list.
**Sort the list**and traverse it from the back.- Select the
**largest frequency**element and decrement it from the array size and**increment**the count of unique elements deleted. - If new array size becomes
**at-least half**of the original array size, return the number of unique elements till now.

Below is the implementation of the above approach:

## C++

`// C++ Program to implement` `// the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` ` ` `// Function to calculate the minimum` ` ` `// elements removed` ` ` `int` `reduceArrSize(` `int` `arr[],` `int` `n)` ` ` `{` ` ` `unordered_map<` `int` `,` `int` `> hm;` ` ` `// Making frequency map of elements` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `hm[arr[i]]++;` ` ` `}` ` ` `// Storing frequencies in a list` ` ` `vector<` `int` `> freq;` ` ` `for` `(` `auto` `it = hm.begin(); it != hm.end(); it++)` ` ` `{` ` ` `freq.push_back(it->second);` ` ` `}` ` ` `// Sorting the list` ` ` `sort(freq.begin(), freq.end());` ` ` `int` `size = n;` ` ` `int` `idx = freq.size() - 1;` ` ` `int` `count = 0;` ` ` `// Counting number of elements to be deleted` ` ` `while` `(size > n/ 2) {` ` ` `size -= arr[idx--];` ` ` `count++;` ` ` `}` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `int` `main()` ` ` `{` ` ` `int` `arr[] = { 2, 2, 2, 2, 4, 4,` ` ` `6, 7, 7, 3, 3, 3 };` ` ` `int` `n = ` `sizeof` `(arr)/` `sizeof` `(arr[0]);` ` ` `int` `count = reduceArrSize(arr, n);` ` ` `cout<<(count);` ` ` `return` `0;` ` ` `}` `// This code is contributed by Potta Lokesh` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to calculate the minimum` ` ` `// elements removed` ` ` `public` `static` `int` `reduceArrSize(` `int` `[] arr)` ` ` `{` ` ` `HashMap<Integer, Integer> hm = ` `new` `HashMap<>();` ` ` `// Making frequency map of elements` ` ` `for` `(` `int` `i = ` `0` `; i < arr.length; i++) {` ` ` `hm.put(arr[i], hm.getOrDefault(arr[i], ` `0` `) + ` `1` `);` ` ` `}` ` ` `// Storing frequencies in a list` ` ` `ArrayList<Integer> freq` ` ` `= ` `new` `ArrayList<Integer>(hm.values());` ` ` `// Sorting the list` ` ` `Collections.sort(freq);` ` ` `int` `size = arr.length;` ` ` `int` `idx = freq.size() - ` `1` `;` ` ` `int` `count = ` `0` `;` ` ` `// Counting number of elements to be deleted` ` ` `while` `(size > arr.length / ` `2` `) {` ` ` `size -= arr[idx--];` ` ` `count++;` ` ` `}` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `[] arr = { ` `2` `, ` `2` `, ` `2` `, ` `2` `, ` `4` `, ` `4` `,` ` ` `6` `, ` `7` `, ` `7` `, ` `3` `, ` `3` `, ` `3` `};` ` ` `int` `count = reduceArrSize(arr);` ` ` `System.out.println(count);` ` ` `}` `}` |

## Python3

`# python 3 Program to implement` `# the above approach` `# Function to calculate the minimum` `# elements removed` `def` `reduceArrSize(arr,n):` ` ` `hm ` `=` `{}` ` ` `# Making frequency map of elements` ` ` `for` `i ` `in` `range` `(n):` ` ` `if` `arr[i] ` `in` `hm:` ` ` `hm[arr[i]] ` `+` `=` `1` ` ` `else` `:` ` ` `hm[arr[i]] ` `=` `1` ` ` `# Storing frequencies in a list` ` ` `freq ` `=` `[]` ` ` `for` `key,value ` `in` `hm.items():` ` ` `freq.append(value)` ` ` `# Sorting the list` ` ` `freq.sort()` ` ` `size ` `=` `n` ` ` `idx ` `=` `len` `(freq) ` `-` `1` ` ` `count ` `=` `0` ` ` `# Counting number of elements to be deleted` ` ` `while` `(size > n` `/` `/` `2` `):` ` ` `size ` `-` `=` `arr[idx]` ` ` `idx ` `-` `=` `1` ` ` `count ` `+` `=` `1` ` ` `return` `count` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `arr ` `=` `[` `2` `, ` `2` `, ` `2` `, ` `2` `, ` `4` `, ` `4` `,` `6` `, ` `7` `, ` `7` `, ` `3` `, ` `3` `, ` `3` `]` ` ` `n ` `=` `len` `(arr)` ` ` `count ` `=` `reduceArrSize(arr, n)` ` ` `print` `(count)` ` ` ` ` `# 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 calculate the minimum` ` ` `// elements removed` ` ` `public` `static` `int` `reduceArrSize(` `int` `[] arr)` ` ` `{` ` ` `Dictionary<` `int` `, ` `int` `> hm = ` `new` `Dictionary<` `int` `, ` `int` `>();` ` ` `// Making frequency map of elements` ` ` `for` `(` `int` `i = 0; i < arr.Length; i++) {` ` ` `if` `(hm.ContainsKey(arr[i])){` ` ` `hm[arr[i]] = hm[arr[i]]+1;` ` ` `}` ` ` `else` `{` ` ` `hm.Add(arr[i], 1);` ` ` `}` ` ` `}` ` ` `// Storing frequencies in a list` ` ` `List<` `int` `> freq` ` ` `= ` `new` `List<` `int` `>(hm.Values);` ` ` `// Sorting the list` ` ` `freq.Sort();` ` ` `int` `size = arr.Length;` ` ` `int` `idx = freq.Count - 1;` ` ` `int` `count = 0;` ` ` `// Counting number of elements to be deleted` ` ` `while` `(size > arr.Length / 2) {` ` ` `size -= arr[idx--];` ` ` `count++;` ` ` `}` ` ` `return` `count;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `int` `[] arr = { 2, 2, 2, 2, 4, 4,` ` ` `6, 7, 7, 3, 3, 3 };` ` ` `int` `count = reduceArrSize(arr);` ` ` `Console.WriteLine(count);` ` ` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to calculate the minimum` `// elements removed` `function` `reduceArrSize(arr)` `{` ` ` `var` `hm = ` `new` `Map();` ` ` ` ` `// Making frequency map of elements` ` ` `for` `(` `var` `i = 0; i < arr.length; i++) {` ` ` `if` `(hm.has(arr[i])){` ` ` `hm.set(arr[i], hm.get(arr[i])+1);` ` ` `}` ` ` `else` `{` ` ` `hm.set(arr[i], 1);` ` ` `}` ` ` `}` ` ` ` ` `// Storing frequencies in a list` ` ` `var` `freq =[ ...hm.values()];` ` ` ` ` `// Sorting the list` ` ` `freq.sort();` ` ` ` ` `var` `size = arr.length;` ` ` `var` `idx = freq.length - 1;` ` ` `var` `count = 0;` ` ` ` ` `// Counting number of elements to be deleted` ` ` `while` `(size > arr.length / 2) {` ` ` `size -= arr[idx--];` ` ` `count++;` ` ` `}` ` ` `return` `count;` `}` `// Driver Code` `var` `arr = [2, 2, 2, 2, 4, 4,` ` ` `6, 7, 7, 3, 3, 3];` `var` `count = reduceArrSize(arr);` `document.write(count);` `// This code is contributed by rutvik_56.` `</script>` |

**Output:**

2

**Time Complexity****: **O(N*logN), sorting the frequency list**Auxiliary Space****: **O(N), hashmap to store the frequencies