Minimum deletions required such that any number X will occur exactly X times | Java Implementation of above approach ; Function to return the minimum deletions required ; To store the frequency of the array elements ; Store frequency of each element ; To store the minimum deletions required ; Value ; It 's frequency ; If number less than or equal to it 's frequency ; Delete extra occurrences ; Delete every occurrence of x ; Driver code
import java . util . * ; class GFG { static int MinDeletion ( int a [ ] , int n ) { Map < Integer , Integer > mp = new HashMap < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( mp . containsKey ( a [ i ] ) ) { mp . put ( a [ i ] , mp . get ( a [ i ] ) + 1 ) ; } else { mp . put ( a [ i ] , 1 ) ; } } int ans = 0 ; for ( Map . Entry < Integer , Integer > i : mp . entrySet ( ) ) { int x = i . getKey ( ) ; int frequency = i . getValue ( ) ; if ( x <= frequency ) { ans += ( frequency - x ) ; } else ans += frequency ; } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 2 , 3 , 2 , 3 , 4 , 4 , 4 , 4 , 5 } ; int n = a . length ; System . out . println ( MinDeletion ( a , n ) ) ; } }