Maximum inversions possible after exactly K removals from given array
Given an array arr[] consisting of N integers, and an integer K, the task is to find the maximum number of inversions of the given array possible after the removal of K array elements.
Examples:
Input: arr[] = {2, 3, 4, 1}, K = 2
Output: 1
Explanation: Removing the 1st and 2nd array elements modifies the array to {4, 1}. Therefore, the maximum number of inversions is 1.Input: arr[] = {4, 3, 2, 1}, K = 3
Output: 0
Explanation: Since the array after K removals will have only 1 element remaining, the maximum number of inversions is 0.
Approach: Follow the steps below to solve the problem:
- Initialize a variable res to store the maximum number of inversions after removing K elements from the array arr[].
- Initialize a binary string S of length N to store which (N – K) elements to be considered from the array arr[].
- Store 0 at [0, K – 1] positions which denote K removed elements, and 1 at [K, N – 1] positions which denote (N – K) selected elements in string S.
- Generate all permutations of string S and do the following:
- Initialize an array v to store the (N – K) selected elements from arr[] in accordance with string S.
- Count the number of inversions in array v and store in cnt.
- Update the res to a maximum of res and cnt.
- After the above steps, print the value of res as the resultant.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number// of inversions after K removalsvoid maximizeInversions(int a[], int n, int k){ // Initialize a binary string string s; // Iterate over range [0, K] for (int i = 0; i < k; i++) { // Append 0 to the string s += "0"; } for (int i = k; i < n; i++) { // Append 1 to the string s += "1"; } // Stores the maximum number of // inversions after K removals int res = 0; // Generate all permutations // of string s do { // Stores the current array vector<int> v; // Stores number of inversions // of the current array int cnt = 0; for (int i = 0; i < n; i++) { if (s[i] == '1') v.push_back(a[i]); } // Find the number of inversions // in the array v for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size(); j++) { // Condition to check if the // number of pairs satisfy // required condition if (v[i] >= v[j]) // Increment the count cnt++; } } // Update res res = max(res, cnt); } while (next_permutation(s.begin(), s.end())); // Print the result cout << res;}// Driver Codeint main(){ int arr[] = { 2, 3, 4, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function Call maximizeInversions(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum number// of inversions after K removalsstatic void maximizeInversions(int a[], int n, int k){ // Initialize a binary String String s=""; // Iterate over range [0, K] for (int i = 0; i < k; i++) { // Append 0 to the String s += "0"; } for (int i = k; i < n; i++) { // Append 1 to the String s += "1"; } // Stores the maximum number of // inversions after K removals int res = 0; // Generate all permutations // of String s do { // Stores the current array Vector<Integer> v = new Vector<>(); // Stores number of inversions // of the current array int cnt = 0; for (int i = 0; i < n; i++) { if (s.charAt(i) == '1') v.add(a[i]); } // Find the number of inversions // in the array v for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size(); j++) { // Condition to check if the // number of pairs satisfy // required condition if (v.get(i) >= v.get(j)) // Increment the count cnt++; } } // Update res res = Math.max(res, cnt); } while (next_permutation(s)); // Print the result System.out.print(res);}static boolean next_permutation(String str){ char []p = str.toCharArray(); for (int a = p.length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.length - 1;; --b) if (p[b] > p[a]) { char t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return false; } return true;}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 3, 4, 1 }; int N = arr.length; int K = 2; // Function Call maximizeInversions(arr, N, K);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachdef next_permutation(Str): p = list(Str) for a in range(len(p) - 2, -1, -1): if p[a] < p[a + 1]: b = len(p) - 1 while True: if p[b] > p[a]: t = p[a] p[a] = p[b] p[b] = t a += 1 b = len(p) - 1 while a < b: t = p[a] p[a] = p[b] p[b] = t a += 1 b -= 1 return False b -= 1 return True# Function to find the maximum number# of inversions after K removalsdef maximizeInversions(a, n, k): # Initialize a binary string s = "" # Iterate over range [0, K] for i in range(k): # Append 0 to the string s += "0" for i in range(k, n): # Append 1 to the string s += "1" # Stores the maximum number of # inversions after K removals res = 0 # Generate all permutations # of string s while (True): # Stores the current array v = [] # Stores number of inversions # of the current array cnt = 0 for i in range(n): if (s[i] == '1'): v.append(a[i]) # Find the number of inversions # in the array v for i in range(len(v) - 1): for j in range(i + 1, len(v)): # Condition to check if the # number of pairs satisfy # required condition if (v[i] >= v[j]): # Increment the count cnt += 1 # Update res res = max(res, cnt) if (not next_permutation(s)): break # Print the result print(res)# Driver Codearr = [ 2, 3, 4, 1 ]N = len(arr)K = 2# Function CallmaximizeInversions(arr, N, K)# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum number// of inversions after K removalsstatic void maximizeInversions(int []a, int n, int k){ // Initialize a binary String String s=""; // Iterate over range [0, K] for (int i = 0; i < k; i++) { // Append 0 to the String s += "0"; } for (int i = k; i < n; i++) { // Append 1 to the String s += "1"; } // Stores the maximum number of // inversions after K removals int res = 0; // Generate all permutations // of String s do { // Stores the current array List<int> v = new List<int>(); // Stores number of inversions // of the current array int cnt = 0; for (int i = 0; i < n; i++) { if (s[i] == '1') v.Add(a[i]); } // Find the number of inversions // in the array v for (int i = 0; i < v.Count - 1; i++) { for (int j = i + 1; j < v.Count; j++) { // Condition to check if the // number of pairs satisfy // required condition if (v[i] >= v[j]) // Increment the count cnt++; } } // Update res res = Math.Max(res, cnt); } while (next_permutation(s)); // Print the result Console.Write(res);}static bool next_permutation(String str){ char []p = str.ToCharArray(); for (int a = p.Length - 2; a >= 0; --a) if (p[a] < p[a + 1]) for (int b = p.Length - 1;; --b) if (p[b] > p[a]) { char t = p[a]; p[a] = p[b]; p[b] = t; for (++a, b = p.Length - 1; a < b; ++a, --b) { t = p[a]; p[a] = p[b]; p[b] = t; } return false; } return true;}// Driver Codepublic static void Main(String[] args){ int []arr = { 2, 3, 4, 1 }; int N = arr.Length; int K = 2; // Function Call maximizeInversions(arr, N, K);}}// This code contributed by Princi Singh |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum number// of inversions after K removalsfunction maximizeInversions(a, n, k){ // Initialize a binary String let s=""; // Iterate over range [0, K] for (let i = 0; i < k; i++) { // Append 0 to the String s += "0"; } for (let i = k; i < n; i++) { // Append 1 to the String s += "1"; } // Stores the maximum number of // inversions after K removals let res = 0; // Generate all permutations // of String s do { // Stores the current array let v = []; // Stores number of inversions // of the current array let cnt = 0; for (let i = 0; i < n; i++) { if (s[i] == '1') v.push(a[i]); } // Find the number of inversions // in the array v for (let i = 0; i < v.length - 1; i++) { for (let j = i + 1; j < v.length; j++) { // Condition to check if the // number of pairs satisfy // required condition if (v[i] >= v[j]) // Increment the count cnt++; } } // Update res res = Math.max(res, cnt); } while (next_permutation(s)); // Print the result document.write(res);}function next_permutation(str){ for (let a = str.length - 2; a >= 0; --a) if (str[a] < str[a + 1]) for (let b = str.length - 1;; --b) if (str[b] > str[a]) { let t = str[a]; str[a] = str[b]; str[b] = t; for (++a, b = str.length - 1; a < b; ++a, --b) { t = str[a]; str[a] = str[b]; str[b] = t; } return false; } return true;}// Driver Code let arr = [ 2, 3, 4, 1 ]; let N = arr.length; let K = 2; // Function Call maximizeInversions(arr, N, K); // This code is contributed by Dharanendra L V. </script> |
Output:
1
Time Complexity: O((N!)*(N – K)2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
