Solve it! A simple coding problem

general
, ,
1

You are given a array and you have to find out number of pairs of elements in it which don’t come in increasing order
eg. in array {1,2,6,3,5}, (6,3) & (6,5) are such pairs. So answer is 2 here.

2

This is same as Counting Inversions.
Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j
See this for more.

1 Like
3

Seeing as what you want, I believe this code for c++ should work fine:

#include <bits/stdc++.h>
using namespace std;
int main() {
int arr = {1, 2, -1, 4, 1, -23, 12};  \\ replace this test case with the array you want
    int size = sizeof(arr)/sizeof(arr[0]);
    int count = 0;
    for(int i = 0; i < size - 1; i++)
    {
        if(arr[i + 1] < arr[i])
        {
            count++;
        }
    }
    return 0;
}
5

What if
A={ 3, 2, 1}
Your code would output 2 while answer is 3 {3,2 3,1 2,1} . You simply need to count inversions

6

You can do this via Divide Conq. ,PBDS, Fenwick Tree etc. This is standard inversion Problem.

7

This is the basic problem of Fenwick tree called inversion in array [google it] learn it from youtube or some blogs over HackerEarth , CP algo , codeforces :slight_smile:

8

Hope the following code helps:

#include
using namespace std;

int main()
{
int n,i,j,count=0;
cin>>n;
int arr[n];
for (i=0;i<n;i++)
cin>>arr[i];
for (i=0;i<n-1;i++)
{
for (j=i+1;j<n;j++)
{
if (arr[i]>arr[j])
count++;
}
}
cout<<count;
return 0;
}

9

The time complexity of your code is O(n^2). It doesn’t execute within time limits if N \ge 10^4.

This would help.

10

Ahhh… now I see we don’t have to count only consecutive elements.
Sorry all, my understanding ability is terrible.