Minimum operations of given type required to empty given array
Given an array arr[] of size N, the task is to find the total count of operations required to remove all the array elements such that if the first element of the array is the smallest element, then remove that element, otherwise move the first element to the end of the array.
Examples:
Input: A[] = {8, 5, 2, 3}
Output: 7
Explanation: Initially, A[] = {8, 5, 2, 3}
Step 1: 8 is not the smallest. Therefore, moving it to the end of the array modifies A[] to {5, 2, 3, 8}.
Step 2: 5 is not the smallest. Therefore, moving it to the end of the array modifies A[] to {2, 3, 8, 5}.
Step 3: 2 is the smallest. Therefore, removing it from the array modifies A[] to {3, 8, 5}
Step 4: 3 is the smallest. Therefore, removing it from the array modifies A[] to A[] = {5, 8}
Step 6: 5 is smallest. Therefore, removing it from the array modifies A[] to {8}
Step 7: 8 is the smallest. Therefore, removing it from the array modifies A[] to {}
Therefore, 7 operations are required to delete the whole array.Input: A[] = {8, 6, 5, 2, 7, 3, 10}
Output: 18
Naive Approach: The simplest approach to solve the problem is to repeatedly check if the first array element is the smallest element of the array or not. If found to be true, then remove that element and increment the count. Otherwise, move the first element of the array to the end of the array and increment the count. Finally, print the total count obtained.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The problem can be efficiently solved using a dynamic programming approach and a sorting algorithm. Follow the steps below to solve the problem:
- Store the elements of array A[] with their indices into a vector of pairs, say vector a.
- Sort the vector according to the values of the elements.
- Initialize arrays countGreater_right[] and countGreater_left[] to store the number of greater elements present in the right of the current element and the number of greater elements present in the left of the current element in the given array respectively which can be done using a set data structure.
- Initially, store the index of starting element of vector a as prev = a[0].second.
- Initialize count with prev+1.
- Now, traverse each element of vector a, from i = 1 to N-1.
- For each element, retrieve its original index as ind = a[i].second and the dp transition for each element is:
If ind > prev, increment count by countGreater_right[prev] – countGreater_right[ind], otherwise
Increment count by countGreater_right[prev] + countGreater_left[ind] + 1.
8. After traversing, print count as the answer.
Below is the implementation of the above algorithm:
C++
#include <bits/stdc++.h> using namespace std; // Function to find the count of greater elements // to right of each index vector< int > countGreaterRight(vector< int >& A, int lenn, vector< int >& countGreater_right) { // Store elements of array in sorted order map< int , int > s; // Traverse the array in reverse order for ( int i = lenn - 1; i >= 0; i--) { int it = distance(s.begin(), s.lower_bound(A[i])); // Stores count of greater elements on the right of i countGreater_right[i] = it; // Insert current element s[A[i]] = 1; } return countGreater_right; } // Function to find the count of greater elements // to left of each index vector< int > countGreaterLeft(vector< int >& A, int lenn, vector< int >& countGreater_left) { // Store elements of array in sorted order map< int , int > s; // Traverse the array in forward order for ( int i = 0; i < lenn; i++) { int it = distance(s.begin(), s.lower_bound(A[i])); // Stores count of greater elements on the left of i countGreater_left[i] = it; // Insert current element s[A[i]] = 1; } return countGreater_left; } // Function to find the count of operations required // to remove all the array elements such that If // 1st elements is smallest then remove the element // otherwise move the element to the end of array void cntOfOperations( int N, vector< int >& A) { // Store {A[i], i} vector<vector< int >> a(N, vector< int >(2)); // Traverse the array for ( int i = 0; i < N; i++) { // Insert {A[i], i} a[i][0] = A[i]; a[i][1] = i; } // Sort the array according to elements of the array, A[] sort(a.begin(), a.end()); // countGreater_right[i]: Stores count of greater elements on the right side of i vector< int > countGreater_right(N); // countGreater_left[i]: Stores count of greater elements on the left side of i vector< int > countGreater_left(N); // Function to fill the arrays countGreater_right = countGreaterRight(A, N, countGreater_right); countGreater_left = countGreaterLeft(A, N, countGreater_left); // Index of smallest element in array A[] int prev = a[0][1], ind = 0; // Stores count of greater element on left side of index i int count = prev; // Iterate over remaining elements in of a[][] for ( int i = 1; i < N; i++) { // Index of next smaller element ind = a[i][1]; // If ind is greater if (ind > prev) { // Update count count += countGreater_right[prev] - countGreater_right[ind]; } else { // Update count count += countGreater_right[prev] + countGreater_left[ind] + 1; } // Update prev prev = ind; } // Print count as total number of operations cout << count+1 << endl; } // Driver Code int main() { // Given array vector< int > A = { 8, 5, 2, 3 }; // Given size int N = A.size(); // Function Call cntOfOperations(N, A); } |
Java
import java.util.*; import java.io.*; public class Main { // Function to find the count of greater elements // to right of each index public static int [] countGreaterRight( int [] A, int lenn, int [] countGreater_right) { // Store elements of array in sorted order TreeMap<Integer, Integer> s = new TreeMap<Integer, Integer>(); // Traverse the array in reverse order for ( int i = lenn - 1 ; i >= 0 ; i--) { int it = s.headMap(A[i]).size(); // Stores count of greater elements on the right of i countGreater_right[i] = it; // Insert current element s.put(A[i], 1 ); } return countGreater_right; } // Function to find the count of greater elements // to left of each index public static int [] countGreaterLeft( int [] A, int lenn, int [] countGreater_left) { // Store elements of array in sorted order TreeMap<Integer, Integer> s = new TreeMap<Integer, Integer>(); // Traverse the array in forward order for ( int i = 0 ; i < lenn; i++) { int it = s.headMap(A[i]).size(); // Stores count of greater elements on the left of i countGreater_left[i] = it; // Insert current element s.put(A[i], 1 ); } return countGreater_left; } // Function to find the count of operations required // to remove all the array elements such that If // 1st elements is smallest then remove the element // otherwise move the element to the end of array public static void cntOfOperations( int N, int [] A) { // Store {A[i], i} int [][] a = new int [N][ 2 ]; // Traverse the array for ( int i = 0 ; i < N; i++) { // Insert {A[i], i} a[i][ 0 ] = A[i]; a[i][ 1 ] = i; } // Sort the array according to elements of the array, A[] Arrays.sort(a, Comparator.comparingInt(o -> o[ 0 ])); // countGreater_right[i]: Stores count of greater elements on the right side of i int [] countGreater_right = new int [N]; // countGreater_left[i]: Stores count of greater elements on the left side of i int [] countGreater_left = new int [N]; // Function to fill the arrays countGreater_right = countGreaterRight(A, N, countGreater_right); countGreater_left = countGreaterLeft(A, N, countGreater_left); // Index of smallest element in array A[] int prev = a[ 0 ][ 1 ], ind = 0 ; // Stores count of greater element on left side of index i int count = prev; // Iterate over remaining elements in of a[][] for ( int i = 1 ; i < N; i++) { // Index of next smaller element ind = a[i][ 1 ]; // If ind is greater if (ind > prev) { // Update count count += countGreater_right[prev] - countGreater_right[ind]; } else { // Update count count += countGreater_right[prev] + countGreater_left[ind] + 1 ; } // Update prev prev = ind; } // Print count as total number of operations System.out.println(count+ 1 ); } // Driver Code public static void main(String[] args) { // Given array int [] A = { 8 , 5 , 2 , 3 }; // Given size int N = A.length; // Function Call cntOfOperations(N, A); } } |
Python3
# Python3 program for the above approach from bisect import bisect_left, bisect_right # Function to find the count of greater # elements to right of each index def countGreaterRight(A, lenn,countGreater_right): # Store elements of array # in sorted order s = {} # Traverse the array in reverse order for i in range (lenn - 1 , - 1 , - 1 ): it = bisect_left( list (s.keys()), A[i]) # Stores count of greater elements # on the right of i countGreater_right[i] = it # Insert current element s[A[i]] = 1 return countGreater_right # Function to find the count of greater # elements to left of each index def countGreaterLeft(A, lenn,countGreater_left): # Store elements of array # in sorted order s = {} # Traverse the array in reverse order for i in range (lenn): it = bisect_left( list (s.keys()), A[i]) # Stores count of greater elements # on the right of i countGreater_left[i] = it # Insert current element s[A[i]] = 1 return countGreater_left # Function to find the count of operations required # to remove all the array elements such that If # 1st elements is smallest then remove the element # otherwise move the element to the end of array def cntOfOperations(N, A): # Store {A[i], i} a = [] # Traverse the array for i in range (N): # Insert {A[i], i} a.append([A[i], i]) # Sort the vector pair according to # elements of the array, A[] a = sorted (a) # countGreater_right[i]: Stores count of # greater elements on the right side of i countGreater_right = [ 0 for i in range (N)] # countGreater_left[i]: Stores count of # greater elements on the left side of i countGreater_left = [ 0 for i in range (N)] # Function to fill the arrays countGreater_right = countGreaterRight(A, N, countGreater_right) countGreater_left = countGreaterLeft(A, N, countGreater_left) # Index of smallest element # in array A[] prev, ind = a[ 0 ][ 1 ], 0 # Stores count of greater element # on left side of index i count = prev # Iterate over remaining elements # in of a[][] for i in range (N): # Index of next smaller element ind = a[i][ 1 ] # If ind is greater if (ind > prev): # Update count count + = countGreater_right[prev] - countGreater_right[ind] else : # Update count count + = countGreater_right[prev] + countGreater_left[ind] + 1 # Update prev prev = ind # Print count as total number # of operations print (count) # Driver Code if __name__ = = '__main__' : # Given array A = [ 8 , 5 , 2 , 3 ] # Given size N = len (A) # Function Call cntOfOperations(N, A) # This code is contributed by mohit kumar 29 |
C#
// C# code addition using System; using System.Collections.Generic; using System.Linq; using System.Collections; public class Program { // Function to find the count of greater elements // to right of each index public static int [] CountGreaterRight( int [] A, int lenn, int [] countGreater_right) { // Store elements of array in sorted order SortedDictionary< int , int > s = new SortedDictionary< int , int >(); // Traverse the array in reverse order for ( int i = lenn - 1; i >= 0; i--) { int it = s.TakeWhile(x => x.Key < A[i]).Count(); // Stores count of greater elements on the right of i countGreater_right[i] = it; // Insert current element s[A[i]] = 1; } return countGreater_right; } // Function to find the count of greater elements // to left of each index public static int [] CountGreaterLeft( int [] A, int lenn, int [] countGreater_left) { // Store elements of array in sorted order SortedDictionary< int , int > s = new SortedDictionary< int , int >(); // Traverse the array in forward order for ( int i = 0; i < lenn; i++) { int it = s.TakeWhile(x => x.Key < A[i]).Count(); // Stores count of greater elements on the left of i countGreater_left[i] = it; // Insert current element s[A[i]] = 1; } return countGreater_left; } // Function to find the count of operations required // to remove all the array elements such that If // 1st elements is smallest then remove the element // otherwise move the element to the end of array public static void CntOfOperations( int N, int [] A) { // Store {A[i], i} int [][] a = new int [N][]; // Traverse the array for ( int i = 0; i < N; i++) { // Insert {A[i], i} a[i] = new int [2] { A[i], i }; } // Sort the array according to elements of the array, A[] Array.Sort(a, (x, y) => x[0].CompareTo(y[0])); // countGreater_right[i]: Stores count of greater elements on the right side of i int [] countGreater_right = new int [N]; // countGreater_left[i]: Stores count of greater elements on the left side of i int [] countGreater_left = new int [N]; // Function to fill the arrays countGreater_right = CountGreaterRight(A, N, countGreater_right); countGreater_left = CountGreaterLeft(A, N, countGreater_left); // Index of smallest element in array A[] int prev = a[0][1], ind = 0; // Stores count of greater element on left side of index i int count = prev; // Iterate over remaining elements in of a[][] for ( int i = 1; i < N; i++) { // Index of next smaller element ind = a[i][1]; // If ind is greater if (ind > prev) { // Update count count += countGreater_right[prev] - countGreater_right[ind]; } else { // Update count count += countGreater_right[prev] + countGreater_left[ind] + 1; } // Update prev prev = ind; } // Print count as total number of operations Console.WriteLine(count+1); } // Driver Code static void Main() { // Given array int [] A = {8, 5, 2, 3}; // Given size int N = A.Length; // Function Call CntOfOperations(N, A); } } // The code is contributed by Nidhi goel. |
Javascript
function countGreaterRight(A, lenn, countGreater_right) { // Store elements of array in sorted order let s = new Map(); // Traverse the array in reverse order for (let i = lenn - 1; i >= 0; i--) { let it = [...s.keys()].filter((x) => x < A[i]).length; // Stores count of greater elements on the right of i countGreater_right[i] = it; // Insert current element s.set(A[i], 1); } return countGreater_right; } function countGreaterLeft(A, lenn, countGreater_left) { // Store elements of array in sorted order let s = new Map(); // Traverse the array in forward order for (let i = 0; i < lenn; i++) { let it = [...s.keys()].filter((x) => x < A[i]).length; // Stores count of greater elements on the left of i countGreater_left[i] = it; // Insert current element s.set(A[i], 1); } return countGreater_left; } function cntOfOperations(N, A) { // Store {A[i], i} let a = []; // Traverse the array for (let i = 0; i < N; i++) { // Insert {A[i], i} a.push([A[i], i]); } // Sort the array according to elements of the array, A[] a.sort((x, y) => x[0] - y[0]); // countGreater_right[i]: Stores count of greater elements on the right side of i let countGreater_right = new Array(N).fill(0); // countGreater_left[i]: Stores count of greater elements on the left side of i let countGreater_left = new Array(N).fill(0); // Function to fill the arrays countGreater_right = countGreaterRight(A, N, countGreater_right); countGreater_left = countGreaterLeft(A, N, countGreater_left); // Index of smallest element in array A[] let prev = a[0][1], ind = 0; // Stores count of greater element on left side of index i let count = prev; // Iterate over remaining elements in of a[][] for (let i = 1; i < N; i++) { // Index of next smaller element ind = a[i][1]; // If ind is greater if (ind > prev) { // Update count count += countGreater_right[prev] - countGreater_right[ind]; } else { // Update count count += countGreater_right[prev] + countGreater_left[ind] + 1; } // Update prev prev = ind; } // Print count as total number of operations console.log(count + 1); } // Driver Code let A = [8, 5, 2, 3]; // Given size let N = A.length; // Function Call cntOfOperations(N, A); |
7
Time Complexity:O(N2)
Auxiliary Space: O(N)
Note: The above approach can be optimized by finding the count of greater elements on the left and right side of each index using Fenwick Tree.