# Number of Inversions

## Problem Statement

\
Given an array of integers. Find the Inversion Count in the array.

Inversion Count: For an array, inversion count indicates how far (or close) the array is from being sorted. If the array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. Formally, two elements a\[i] and a\[j] form an inversion if a\[i] > a\[j] and i < j.

## Intuition

```
Approach :

Sort the array and check

2 3 4 5     1 2 3
Check that 2 is greater than 1 so 2 3 4 5 all greater than 1
So on 
We use Merge sort for this 
```

### Links

<https://www.codingninjas.com/studio/problems/number-of-inversions_6840276?utm_source=striver&utm_medium=website&utm_campaign=a_zcoursetuf&leftPanelTabValue=PROBLEM>

### Video Links

<https://www.youtube.com/watch?v=AseUmwVNaoY&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
int merge(vector<int>&arr, int low, int mid, int high){
    vector<int> temp;
    int left = low;
    int right = mid+1;
    int ct = 0;

    while(left<=mid and right<=high){
        if(arr[left]<=arr[right]){
            temp.push_back(arr[left]);
            left++;
        }
        else{
            temp.push_back(arr[right]);
            ct += (mid-left+1);
            right++;
        }
    }

    while (left <= mid) {
        temp.push_back(arr[left]);
        left++;
    }

    while (right <= high) {
        temp.push_back(arr[right]);
        right++;
    }

    for (int i=low; i<=high; i++) {
        arr[i] = temp[i - low];
    }

    return ct;
}


int mergesort(vector<int>&arr, int low, int high){
    int ct = 0;
    if(low >= high)
        return ct;
    int mid = (low + high)/2;
    ct += mergesort(arr, low, mid);
    ct += mergesort(arr, mid+1, high);
    ct += merge(arr, low, mid, high);

    return ct;
}

int numberOfInversions(vector<int>&arr, int n) {
    return mergesort(arr, 0, arr.size()-1);
}
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/array/hard/number-of-inversions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.