#include <bits/stdc++.h>
long long getInversions(long long *arr, int n){
int count = 0;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
if(arr[i] > arr[j]) count++;
}
}
return count;
}
Problem of the day
For a given integer array/list 'ARR' of size 'N' containing all distinct values, find the total number of 'Inversions' that may exist.
An inversion is defined for a pair of integers in the array/list when the following two conditions are met.
A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:
1. 'ARR[i] > 'ARR[j]'
2. 'i' < 'j'
Where 'i' and 'j' denote the indices ranging from [0, 'N').
The first line of input contains an integer 'N', denoting the size of the array.
The second line of input contains 'N' integers separated by a single space, denoting the elements of the array 'ARR'.
Output format :
Print a single line containing a single integer that denotes the total count of inversions in the input array.
Note:
You are not required to print anything, it has been already taken care of. Just implement the given function.
1 <= N <= 10^5
1 <= ARR[i] <= 10^9
Where 'ARR[i]' denotes the array element at 'ith' index.
Time Limit: 1 sec
3
3 2 1
3
We have a total of 3 pairs which satisfy the condition of inversion. (3, 2), (2, 1) and (3, 1).
5
2 5 1 3 4
4
We have a total of 4 pairs which satisfy the condition of inversion. (2, 1), (5, 1), (5, 3) and (5, 4).
1. Start with the brute force approach.
2. Use a modified merge sort.
3. Iterate through the elements in sorted order and use a Fenwick tree to track the inversions.
The steps are as follows:
O(N ^ 2), Where ‘N’ is the total number of elements in the array.
Since for every element, we iterate over the remaining elements on right side, which makes it polynomial time. Thus the time complexity will be O(N ^ 2).
O(1).
Since constant space is used. Thus the space complexity will be O(1).
Interview problems
Easy C++ Solution | Nested For Loops
#include <bits/stdc++.h>
long long getInversions(long long *arr, int n){
int count = 0;
for(int i=0; i<n; i++) {
for(int j=i+1; j<n; j++) {
if(arr[i] > arr[j]) count++;
}
}
return count;
}
Interview problems
Solution for Count Inversion having Time Complexity : O(N log N) and Space Complexity : O( N )
import java.util.*;
import java.io.*;
public class Solution {
private static long mergeAndCount(long[] arr, int left, int mid, int right) {
long[] leftArray = Arrays.copyOfRange(arr, left, mid + 1);
long[] rightArray = Arrays.copyOfRange(arr, mid + 1, right + 1);
int i = 0, j = 0;
long count = 0;
int k = left;
while (i < leftArray.length && j < rightArray.length) {
if (leftArray[i] <= rightArray[j]) {
arr[k++] = leftArray[i++];
} else {
arr[k++] = rightArray[j++];
count += (leftArray.length - i); // Count inversions
}
}
while (i < leftArray.length) {
arr[k++] = leftArray[i++];
}
while (j < rightArray.length) {
arr[k++] = rightArray[j++];
}
return count;
}
private static long mergeSortAndCount(long[] arr, int left, int right) {
long count = 0;
if (left < right) {
int mid = (left + right) / 2;
count += mergeSortAndCount(arr, left, mid);
count += mergeSortAndCount(arr, mid + 1, right);
count += mergeAndCount(arr, left, mid, right);
}
return count;
}
public static long getInversions(long arr[], int n) {
return mergeSortAndCount(arr, 0, n - 1);
}
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextLong();
}
System.out.println(getInversions(arr, n));
}
}
Interview problems
brute force approach.
#include <bits/stdc++.h>
long long getInversions(long long *arr, int n){
// Write your code here.
long long count=0;
for(int i=0;i<n;i++){
for(int j=n-1;j>=0;j--){
if((arr[i]>arr[j]) && i<j){
count++;
}
}
}
return count;
}
Interview problems
Java Easy Solution
import java.util.* ;
import java.io.*;
public class Solution {
private static long merge(long arr[], int low, int mid, int high){
ArrayList<Long> temp = new ArrayList<>();
int left = low;
int right = mid+1;
long count = 0;
while(left <= mid && right <= high){
if(arr[left] <= arr[right]){
temp.add(arr[left]);
left++;
} else {
temp.add(arr[right]);
count += (mid - left + 1);
right++;
}
}
while(left <= mid){
temp.add(arr[left]);
left++;
}
while(right <= high){
temp.add(arr[right]);
right++;
}
for(int i=low; i<=high; i++){
arr[i] = temp.get(i - low);
}
return count;
}
private static long mergeSort(long arr[], int low, int high){
long count = 0;
if(low >= high) return count;
int mid = (low + high) / 2;
count += mergeSort(arr, low, mid);
count += mergeSort(arr, mid+1, high);
count += merge(arr, low, mid, high);
return count;
}
public static long getInversions(long arr[], int n) {
return mergeSort(arr, 0, n-1);
}
}
Interview problems
EASY C++ CODE with SORTING and BINARY SEARCH
Description of the Code
The function getInversions calculates the number of inversions in an array, where an inversion is defined as a pair of indices (i, j) such that i < j and arr[i] > arr[j].
Explanation:
Initialization:
Sorting:
Counting Inversions:
Returning the Result:
Complexity
Note: This code counts the inversions based on the sorted positions of elements. By removing elements from the vector after each iteration, it ensures that elements are not double-counted.
C++ CODE
#include <bits/stdc++.h>
long long getInversions(long long *arr, int n) {
// Initialize a vector to store elements of the array
vector<long long> v;
// Copy elements from the array into the vector
for(int i = 0; i < n; i++) {
v.push_back(arr[i]);
}
long long ans = 0; // Variable to store the count of inversions
// Sort the vector. This helps in finding the position of elements efficiently.
sort(v.begin(), v.end());
// Iterate over each element in the array to count inversions
for (int i = 0; i < n; i++) {
long long a = arr[i];
// Find the position of the current element 'a' in the sorted vector 'v'
auto it = lower_bound(v.begin(), v.end(), a);
// Calculate the index of the element 'a' in the sorted vector
int b = it - v.begin();
// Add this index to the inversion count
ans += b;
// Remove the element from the sorted vector to prevent counting it again
v.erase(v.begin() + b);
}
return ans; // Return the total number of inversions
}
Interview problems
JAVA BEST SOLUTION || Count Inversions ||
import java.util.* ;
import java.io.*;
public class Solution {
public static long getInversions(long arr[], int n) {
long count = sort(arr, 0, n-1);
return count;
}
public static long sort(long arr[], int left, int right) {
long count = 0;
if (left >= right) {
return count;
}
int mid = left + right >> 1;
count += sort(arr, left, mid);
count += sort(arr, mid + 1, right);
count += merge(arr, left, mid, right);
return count;
}
public static long merge(long[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
long[] leftArr = new long[n1];
long[] rightArr = new long[n2];
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightArr[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = left, count = 0;
while (i < n1 && j < n2) {
if (leftArr[i] < rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
count += n1 - i;
j++;
}
k++;
}
while (i < leftArr.length) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < rightArr.length) {
arr[k] = rightArr[j];
j++;
k++;
}
return count;
}
}
Interview problems
Java Easy to Understand Solution
import java.util.* ;
import java.io.*;
public class Solution {
public static long getInversions(long arr[], int n) {
long count = sort(arr, 0, n-1);
return count;
}
public static long sort(long arr[], int left, int right) {
long count = 0;
if (left >= right) {
return count;
}
int mid = left + right >> 1;
count += sort(arr, left, mid);
count += sort(arr, mid + 1, right);
count += merge(arr, left, mid, right);
return count;
}
public static long merge(long[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
long[] leftArr = new long[n1];
long[] rightArr = new long[n2];
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[left + i];
}
for (int i = 0; i < n2; i++) {
rightArr[i] = arr[mid + 1 + i];
}
int i = 0, j = 0, k = left, count = 0;
while (i < n1 && j < n2) {
if (leftArr[i] < rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
count += n1 - i;
j++;
}
k++;
}
while (i < leftArr.length) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < rightArr.length) {
arr[k] = rightArr[j];
j++;
k++;
}
return count;
}
}
Interview problems
C++ simple TC:O(N^2) solution SC:O(1)
#include <bits/stdc++.h>
long long getInversions(long long *arr, int n){
// Write your
int cnt=0;
for(int i=0;i<n;i++)
{
for(int j=1;j<n;j++)
{
if (i < j) {
if (arr[i] > arr[j])
cnt++;
}
}
}
return cnt;
}
Interview problems
✅BETTER THAN 100%🔥MERGE SORT🔥
#include <bits/stdc++.h>
int cnt=0;
void merge(vector<int> &arr,int low,int mid,int high){
vector<int> temp;
int left=low;
int right=mid+1;
while(left<=mid && right<=high){
if(arr[left]<=arr[right]){
temp.push_back(arr[left]);
left++;
}
else{
temp.push_back(arr[right]);
cnt+=(mid-left+1);
right++;
}
}
while(left<=mid){
temp.push_back(arr[left]);
left++;
}
while(right<=high){
temp.push_back(arr[right]);
right++;
}
int idx=0;
for(int i=low;i<=high;i++){
arr[i]=temp[idx++];
}
}
void mS(vector<int> &arr,int low,int high){
if(low==high){
return;
}
int mid=(low+high)/2;
mS(arr,low,mid);
mS(arr,mid+1,high);
merge(arr,low,mid,high);
}
int getInversions(vector<int> &arr, int n){
mS(arr,0,n-1);
return cnt;
}
Interview problems
how can we modified this code
#include <bits/stdc++.h>
long long getInversions(long long *arr, int n){
// Write your code here.
long long count=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(i<j && arr[i]>arr[j]){
count++;
}
}
}
return count;
}