Minimize consecutive removals of elements of the same type to empty given array
Given an array A[ ] consisting of N positive integers, such that each array element Ai denotes the count of elements of ith type, the task is to minimize the number of deletions of consecutive elements of the same type to empty the given array.
Examples:
Input : A[ ] = {3, 3, 2}
Output: 0
Explanation: The array consists of 3, 3, 2 elements of 1st, 2nd and 3rd type respectively. By removing the array elements in the order {2, 1, 2, 3, 1, 3, 1}, a sequence is obtained in which no two consecutive elements are removed which are of the same type. Therefore, the count is 0.Input: A [ ] = {1, 4, 1}
Output: 1
Explanation: The array consists of 1, 4, 1 elements of 1st, 2nd and 3rd type respectively. By removing the array elements in the order { 2, 3, 2, 2, 1, 2}, consecutive deletions of same type elements is reduced to 1. Therefore, the count is 1.
Approach: The problem can be solved by Greedy Approach. Follow the steps below to solve the problem:
- Sort the given array.
- Calculate the sum of the elements of the array.
- Find the largest element present in the array, which is AN-1..
- If the difference between sum and maximum element is greater than the maximum element, print 0 as the required answer.
- Otherwise, print 2* max – sum -1 as the required answer.
Below is the implementation of the above approach.
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum consecutive // removals of elements of the same type void minRemovals( int A[], int N) { // Sort the array sort(A, A + N); // Stores the maximum element // present in the array int mx = A[N - 1]; // Stores sum of the array int sum = 1; // Calculate sum of the array for ( int i = 0; i < N; i++) { sum += A[i]; } if (sum - mx >= mx) { cout << 0 << "\n" ; } else { cout << 2 * mx - sum << "\n" ; } } // Driver Code int main() { int A[] = { 3, 3, 2 }; int N = sizeof (A) / sizeof (A[0]); // Function call minRemovals(A, N); return 0; } |
Java
// Java implementation of the above approach import java.util.Arrays; class GFG { // Function to count minimum consecutive // removals of elements of the same type static void minRemovals( int []A, int N) { // Sort the array Arrays.sort(A); // Stores the maximum element // present in the array int mx = A[N - 1 ]; // Stores sum of the array int sum = 1 ; // Calculate sum of the array for ( int i = 0 ; i < N; i++) { sum += A[i]; } if (sum - mx >= mx) { System.out.println( 0 ); } else { System.out.println( 2 * mx - sum); } } // Driver Code public static void main(String[] args) { int []A = { 3 , 3 , 2 }; int N = A.length; // Function call minRemovals(A, N); } } // This code is contributed by AnkThon |
Python3
# Python3 implementation of the above approach # Function to count minimum consecutive # removals of elements of the same type def minRemovals(A, N): # Sort the array A.sort() # Stores the maximum element # present in the array mx = A[N - 1 ] # stores the sum of array sum = 1 # Calculate sum of array for i in range ( 0 , N): sum + = A[i] if (( sum - mx) > = mx): print ( 0 , end = "") else : print ( 2 * mx - sum , end = "") # Driver Code if __name__ = = "__main__" : A = [ 3 , 3 , 2 ] N = len (A) # Function call minRemovals(A, N) # This code is contributed by Virusbuddah |
C#
// C# implementation of the above approach using System; class GFG { // Function to count minimum consecutive // removals of elements of the same type static void minRemovals( int []A, int N) { // Sort the array Array.Sort(A); // Stores the maximum element // present in the array int mx = A[N - 1]; // Stores sum of the array int sum = 1; // Calculate sum of the array for ( int i = 0; i < N; i++) { sum += A[i]; } if (sum - mx >= mx) { Console.WriteLine(0); } else { Console.WriteLine(2 * mx - sum); } } // Driver Code public static void Main(String[] args) { int []A = { 3, 3, 2 }; int N = A.Length; // Function call minRemovals(A, N); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for above approach // Function to count minimum consecutive // removals of elements of the same type function minRemovals(A, N) { // Sort the array A.sort(); // Stores the maximum element // present in the array let mx = A[N - 1]; // Stores sum of the array let sum = 1; // Calculate sum of the array for (let i = 0; i < N; i++) { sum += A[i]; } if (sum - mx >= mx) { document.write(0); } else { document.write(2 * mx - sum); } } // Driver Code let A = [3, 3, 2 ]; let N = A.length; // Function call minRemovals(A, N); // This code is contributed by avijitmondal1998. </script> |
0
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us