Inversion of array

QUESTION

Given an array, find inversion count of array.\n\nInversion Count for an array indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. \nFormally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.\nThe sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).\n\nInput:\n\nThe first line of input contains an integer T denoting the number of test cases.\nThe first line of each test case is N,N is the size of array.\nThe second line of each test case contains N input C[i].\n\nOutput:\n\nPrint the inversion count of array.\n\nConstraints:\n\n1<=T<=100\n1<=N<=100\n1<=C<=500.

“TESTCASE_1”: “1\n5\n2 4 1 3 5\n###—###SEPERATOR—###—\n3”, “TESTCASE_2”: “1\n4\n2 4 1 0\n###—###SEPERATOR—###—\n5”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <stdio.h>
int getInvCount(int arr[], int n)
{
  int inv_count = 0, i, j;
  for (i = 0; i < n - 1; i++)
  {
    for (j = i+1; j < n; j++)
    {
      if (arr[i] > arr[j])
      {
        inv_count++;
      }
    }
  }

  return inv_count;
}

/* Driver progra to test above functions */
int main(int argv, char** args)
{
  int arr[10], i, j, n, m;
  scanf("%d", &m);
  scanf("%d", &n);
  for(i=0;i<n;i++)
  {
    scanf("%d", &arr[i]);
  }
  printf("%d\n", getInvCount(arr, n));
  return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.