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.
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
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.
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; }
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
You can do this via Divide Conq. ,PBDS, Fenwick Tree etc. This is standard inversion Problem.
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
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;
}
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.
Ahhh… now I see we don’t have to count only consecutive elements.
Sorry all, my understanding ability is terrible.