Maximum inversions possible after exactly K removals from given array

0 0 8 minutes read

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 1^st and 2^nd 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 removals
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<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 Code
int 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 approach
import java.util.*;
 
class GFG
{
 
// Function to find the maximum number
// of inversions after K removals
static 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 Code
public 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 approach
def 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 removals
def 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 Code
arr = [ 2, 3, 4, 1 ]
N = len(arr)
K = 2
 
# Function Call
maximizeInversions(arr, N, K)
 
# This code is contributed by divyeshrabadiya07

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find the maximum number
// of inversions after K removals
static 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 Code
public 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 removals
function 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:

Time Complexity: O((N!)*(N – K)²)
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!