Given an array of n distinct integers 
and an integer k. Find out the number of sub-sequences of a such that 
, and 
. In other words output the total number of inversions of length k. Examples:
Input : a[] = {9, 3, 6, 2, 1}, k = 3
Output : 7
The seven inversions are {9, 3, 2}, {9, 3, 1},
{9, 6, 2}, {9, 6, 1}, {9, 2, 1}, {3, 2, 1} and
{6, 2, 1}.
Input : a[] = {5, 6, 4, 9, 2, 7, 1}, k = 4
Output : 2
The two inversions are {5, 4, 2, 1}, {6, 4, 2, 1}.
We have already discussed counting inversion of length three here. This post will generalise the approach using Binary Indexed Tree and Counting inversions using BIT. More on Binary Indexed Trees can be found from the actual paper that Peter M. Fenwick published, here. 1. To begin with, we first convert the given array to a permutation of elements 
(Note that this is always possible since the elements are distinct). 2. The approach is to maintain a set of k Fenwick Trees. Let it be denoted by ![bit[k][n]](https://geeksforgeeks.org/wp-content/uploads/2023/10/dominic_rubhabha_quicklatex.com-2e90d75d930f6ef5e0856c1e6e66a9d0_l3.png "Rendered by QuickLaTeX.com")
where ![bit[l][x]](https://geeksforgeeks.org/wp-content/uploads/2023/10/wardslaus_rubhabha_quicklatex.com-bc1016ecc3c8f61b0081eec43eac60b9_l3.png "Rendered by QuickLaTeX.com")
, keeps track of the number of 
– length sub-sequences that start with 
. 3. We iterate from the end of the converted array to the beginning. For every converted array element , we update the Fenwick tree set, as: For each 
, each sub-sequence of length that start with a number less than is also a part of sequences of length 
. The final result is found by sum of occurrences of 
. The implementation is discussed below:
C++
// C++ program to count inversions of size k using// Binary Indexed Tree#include <bits/stdc++.h>using namespace std;// It is beneficial to declare the 2D BIT globally // since passing it into functions will create // additional overheadconst int K = 51;const int N = 100005;int BIT[K][N] = { 0 };// update function. "t" denotes the t'th Binary // indexed treevoid updateBIT(int t, int i, int val, int n){ // Traversing the t'th BIT while (i <= n) { BIT[t][i] = BIT[t][i] + val; i = i + (i & (-i)); }}// function to get the sum.// "t" denotes the t'th Binary indexed treeint getSum(int t, int i){ int res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t][i]; i = i - (i & (-i)); } return res;}// Converts an array to an array with values from 1 to n// and relative order of smaller and greater elements // remains same. For example, {7, -90, 100, 1} is// converted to {3, 1, 4, 2 }void convert(int arr[], int n){ // Create a copy of arr[] in temp and sort // the temp array in increasing order int temp[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; sort(temp, temp + n); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns pointer to the // first element greater than or equal // to arr[i] arr[i] = lower_bound(temp, temp + n, arr[i]) - temp + 1; }}// Returns count of inversions of size threeint getInvCount(int arr[], int n, int k){ // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted array in // reverse order. for (int i = n - 1; i >= 0; i--) { int x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (int l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n);}// Driver program to test above functionint main(){ int arr[] = { 5, 6, 4, 9, 3, 7, 2, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 4; cout << "Inversion Count : " << getInvCount(arr, n, k); return 0;} |
Java
// Java program to count // inversions of size k using// Binary Indexed Treeimport java.io.*;import java.util.Arrays;import java.util.ArrayList;import java.lang.*;import java.util.Collections;class GFG{// It is beneficial to declare// the 2D BIT globally since // passing it into functions // will create additional overheadstatic int K = 51;static int N = 100005;static int BIT[][] = new int[K][N];// update function. "t" denotes // the t'th Binary indexed treestatic void updateBIT(int t, int i, int val, int n){ // Traversing the t'th BIT while (i <= n) { BIT[t][i] = BIT[t][i] + val; i = i + (i & (-i)); }}// function to get the sum.// "t" denotes the t'th // Binary indexed treestatic int getSum(int t, int i){ int res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t][i]; i = i - (i & (-i)); } return res;}// Converts an array to an // array with values from// 1 to n and relative order// of smaller and greater // elements remains same. // For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 }static void convert(int arr[], int n){ // Create a copy of arr[] in // temp and sort the temp // array in increasing order int temp[] = new int[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; Arrays.sort(temp); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns // pointer to the first // element greater than // or equal to arr[i] arr[i] = Arrays.binarySearch(temp, arr[i]) + 1; }}// Returns count of inversions// of size threestatic int getInvCount(int arr[], int n, int k){ // Convert arr[] to an array // with values from 1 to n and // relative order of smaller // and greater elements remains // same. For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted // array in reverse order. for (int i = n - 1; i >= 0; i--) { int x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (int l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n);}// Driver Codepublic static void main(String[] args){ int arr[] = { 5, 6, 4, 9, 3, 7, 2, 1 }; int n = arr.length; int k = 4; System.out.println("Inversion Count : " + getInvCount(arr, n, k));}} |
Python3
# Python3 program to count inversions # of size k using Binary Indexed Tree # It is beneficial to declare the 2D BIT # globally since passing it o functions # will create additional overhead K = 51N = 100005BIT = [[0 for x in range(N)] for y in range(K)] # update function. "t" denotes# the t'th Binary indexed tree def updateBIT(t, i, val, n): # Traversing the t'th BIT while (i <= n): BIT[t][i] = BIT[t][i] + val i = i + (i & (-i)) # function to get the sum. "t" denotes # the t'th Binary indexed tree def getSum(t, i): res = 0 # Traversing the t'th BIT while (i > 0): res = res + BIT[t][i] i = i - (i & (-i)) return res # Converts an array to an array with # values from 1 to n and relative order # of smaller and greater elements remains# same. For example, 7, -90, 100, 1 is # converted to 3, 1, 4, 2 def convert( arr, n): # Create a copy of arr[] in temp and sort # the temp array in increasing order temp = [0] * n for i in range(n): temp[i] = arr[i] temp = sorted(temp) j = 1 for i in temp: arr[arr.index(i)] = j j += 1# Returns count of inversions # of size three def getInvCount(arr, n, k) : # Convert arr[] to an array with # values from 1 to n and relative # order of smaller and greater elements # remains same. For example, 7, -90, 100, 1 # is converted to 3, 1, 4, 2 convert(arr, n) # iterating over the converted array # in reverse order. for i in range(n - 1, -1, -1): x = arr[i] # update the BIT for l = 1 updateBIT(1, x, 1, n) # update BIT for all other BITs for l in range(1, k): updateBIT(l + 1, x, getSum(l, x - 1), n) # final result return getSum(k, n) # Driver code if __name__ =="__main__": arr = [5, 6, 4, 9, 3, 7, 2, 1] n = 8 k = 4 print("Inversion Count :", getInvCount(arr, n, k)) # This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
// C# program to count // inversions of size k using // Binary Indexed Tree using System;using System.Linq;class GFG { // It is beneficial to declare // the 2D BIT globally since // passing it into functions // will create additional overhead static int K = 51; static int N = 100005; static int [,]BIT = new int[K, N]; // update function. "t" denotes // the t'th Binary indexed tree static void updateBIT(int t, int i, int val, int n) { // Traversing the t'th BIT while (i <= n) { BIT[t, i] = BIT[t, i] + val; i = i + (i & (-i)); } } // function to get the sum. // "t" denotes the t'th // Binary indexed tree static int getSum(int t, int i) { int res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t, i]; i = i - (i & (-i)); } return res; } // Converts an array to an // array with values from // 1 to n and relative order // of smaller and greater // elements remains same. // For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } static void convert(int []arr, int n) { // Create a copy of arr[] in // temp and sort the temp // array in increasing order int []temp = new int[n]; for (int i = 0; i < n; i++) temp[i] = arr[i]; Array.Sort(temp); // Traverse all array elements for (int i = 0; i < n; i++) { // lower_bound() Returns // pointer to the first // element greater than // or equal to arr[i] arr[i] = Array.BinarySearch(temp, arr[i]) + 1; } } // Returns count of inversions // of size three static int getInvCount(int []arr, int n, int k) { // Convert arr[] to an array // with values from 1 to n and // relative order of smaller // and greater elements remains // same. For example, {7, -90, 100, 1} // is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted // array in reverse order. for (int i = n - 1; i >= 0; i--) { int x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (int l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n); } // Driver Code public static void Main(String[] args) { int []arr = { 5, 6, 4, 9, 3, 7, 2, 1 }; int n = arr.Length; int k = 4; Console.WriteLine("Inversion Count : " + getInvCount(arr, n, k)); } } // This code is contributed by PrinciRaj1992 |
Javascript
// Javascript program to count inversions of size k using// Binary Indexed Tree// It is beneficial to declare the 2D BIT globally// since passing it into functions will create// additional overheadlet K = 51;let N = 100005;let BIT = new Array(K).fill(0).map(() => new Array(N).fill(0));// update function. "t" denotes the t'th Binary// indexed treefunction updateBIT(t, i, val, n){ // Traversing the t'th BIT while (i <= n) { BIT[t][i] = BIT[t][i] + val; i = i + (i & (-i)); }}// function to get the sum.// "t" denotes the t'th Binary indexed treefunction getSum(t, i){ let res = 0; // Traversing the t'th BIT while (i > 0) { res = res + BIT[t][i]; i = i - (i & (-i)); } return res;}// Converts an array to an array with values from 1 to n// and relative order of smaller and greater elements// remains same. For example, {7, -90, 100, 1} is// converted to {3, 1, 4, 2 }function convert(arr, n){ // Create a copy of arr[] in temp and sort // the temp array in increasing order let temp=new Array(n); for (let i = 0; i < n; i++) temp[i] = arr[i]; temp.sort(); // Traverse all array elements for (let i = 0; i < n; i++) { // lower_bound() Returns pointer to the // first element greater than or equal // to arr[i] arr[i] = lower_bound(temp, 0, n, arr[i])+1; }}function lower_bound(a, low, high, element){ while(low < high) { let middle = low + parseInt((high - low) / 2, 10); if(element > a[middle]) low = middle + 1; else high = middle; } return low;}// Returns count of inversions of size threefunction getInvCount(arr, n, k){ // Convert arr[] to an array with values from // 1 to n and relative order of smaller and // greater elements remains same. For example, // {7, -90, 100, 1} is converted to {3, 1, 4, 2 } convert(arr, n); // iterating over the converted array in // reverse order. for (let i = n - 1; i >= 0; i--) { let x = arr[i]; // update the BIT for l = 1 updateBIT(1, x, 1, n); // update BIT for all other BITs for (let l = 1; l < k; l++) { updateBIT(l + 1, x, getSum(l, x - 1), n); } } // final result return getSum(k, n);}// Driver program to test above function let arr = [ 5, 6, 4, 9, 3, 7, 2, 1 ]; let n = arr.length; let k = 4; console.log("Inversion Count : " + getInvCount(arr, n, k)); // This code is contributed by Pushpesh Raj. |
Output:
Inversion Count : 11
Time Complexity 
Auxiliary Space 
It should be noted that this is not the only approach to solve the problem of finding k-inversions. Obviously, any problem solvable by BIT is also solvable by Segment Tree. Besides, we can use Merge-Sort based algorithm, and C++ policy based data structure too. Also, at the expense of higher time complexity, Dynamic Programming approach can also be used.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
