Minimize removals required to make given Array consecutive in any order
Given an array arr[]. The task is to minimize the number of removals to make all the elements in arr[] consecutive.
Examples
Input: arr[] = {45, 42, 46, 48, 47}
Output: 1
Explanation: After removing 42 we see that there is a consecutive elements present in the array(45-48).Input: arr[] = {7, 4, 8, 5, 9 }
Output: 2
Explanation: After removing 4 and 5 we see that there is a consecutive elements present in the array(7-9).
Approach: This problem can be solved by using Hashmaps. Follow the steps below to solve the given problem.
- Firstly create a map and at every element i.e at every key put its value true.
- So each element/key has true value. Now move through the keyset of the map and see if it contains (key-1) in the map.
- If it is then put false at that key.
- Now in another loop, work for that keys whose value is true and go till its longest sequence and find the length of the longest consecutive sequence.
- So the minimum number of removals will be the difference in length of array and length of the longest consecutive sequence.
Follow the steps below to solve the given problem.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; void minRemovalsConsecutive(vector< int >& a, int n) { // Hashmap to store the elements // in key-value pairs map< int , bool > map; for ( int val : a) { map[val] = true ; } for ( auto it = map.begin(); it != map.end(); ++it) { if (map.count(it->first - 1)) { map[it->first] = false ; } } int max = 0; // Iterating for all keys in map for ( auto it = map.begin(); it != map.end(); ++it) { if (map.count(it->first)) { int t1 = 1; while (map.count(it->first + t1)) { t1++; } if (t1 > max) { max = t1; } } } // Printing the final answer cout << (n - max); } // Driver Code int main() { int N = 5; vector< int > arr = { 45, 42, 46, 48, 47 }; // Function Call minRemovalsConsecutive(arr, N); return 0; } // This code is contributed by rakeshsahni |
Java
// Java program for above approach import java.io.*; import java.util.*; class GFG { public static void minRemovalsConsecutive( int a[], int n) { // Hashmap to store the elements // in key-value pairs HashMap<Integer, Boolean> map = new HashMap<>(); for ( int val : a) { map.put(val, true ); } for ( int val : map.keySet()) { if (map.containsKey(val - 1 )) { map.put(val, false ); } } int max = 0 ; // Iterating for all keys in map for ( int val : map.keySet()) { if (map.get(val)) { int t1 = 1 ; while (map.containsKey(val + t1)) { t1++; } if (t1 > max) { max = t1; } } } // Printing the final answer System.out.println(n - max); } // Driver Code public static void main(String[] args) { int N = 5 ; int arr[] = { 45 , 42 , 46 , 48 , 47 }; // Function Call minRemovalsConsecutive(arr, N); } } |
Python3
# Python 3 program for above approach def minRemovalsConsecutive(a, n): # Hashmap to store the elements # in key-value pairs map = {} for val in a: map [val] = True for it in map : if ((it - 1 ) in map ): map [it] = False max = 0 # Iterating for all keys in map for it in map : if (it in map ): t1 = 1 while ((it + t1) in map ): t1 + = 1 if (t1 > max ): max = t1 # Printing the final answer print (n - max ) # Driver Code if __name__ = = "__main__" : N = 5 arr = [ 45 , 42 , 46 , 48 , 47 ] # Function Call minRemovalsConsecutive(arr, N) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static void minRemovalsConsecutive( int []a, int n) { // Hashmap to store the elements // in key-value pairs Dictionary< int , bool > map1 = new Dictionary< int , bool >(); foreach ( int val in a) { map1.Add(val, true ); } Dictionary< int , bool > map2 = new Dictionary< int , bool >(); foreach (KeyValuePair< int , bool > k in map1){ if (map1.ContainsKey(k.Key - 1)) { map2.Add(k.Key, false ); } else { map2.Add(k.Key, true ); } } int max = 0; // Iterating for all keys in map foreach (KeyValuePair< int , bool > k in map2){ if (map2.ContainsKey(k.Key)) { int t1 = 1; while (map2.ContainsKey(k.Key + t1)) { t1++; } if (t1 > max) { max = t1; } } } // Printing the final answer Console.WriteLine(n - max); } // Driver Code public static void Main() { int N = 5; int []arr = { 45, 42, 46, 48, 47 }; // Function Call minRemovalsConsecutive(arr, N); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for above approach function minRemovalsConsecutive(a, n) { // Hashmap to store the elements // in key-value pairs let map = new Map(); for (val of a) { map.set(val, true ); } for (let it of map.keys()) { if (map.has(it - 1)) { map.set(it, false ); } } let max = 0; // Iterating for all keys in map for (val of map.keys()) { if (map.get(val)) { let t1 = 1; while (map.has(val + t1)) { t1++; } if (t1 > max) { max = t1; } } } // Printing the final answer document.write((n - max)); } // Driver Code let N = 5; let arr = [45, 42, 46, 48, 47]; // Function Call minRemovalsConsecutive(arr, N); // This code is contributed by gfgking </script> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us