fork(1) download
copy 
  1. import java.util.*;
  2. //Uses a modified Merge-Sort Algorithm to calculate number of inversions
  3. class soln
  4. {
  5. 	//Modified Merge method.
  6. 	static long merge(int[] arr, int[] left, int[] right) {
  7.     int i = 0, j = 0;
  8.     long count = 0; //Initialize
  9.     while (i < left.length || j < right.length) {  
  10.     	//Loop till all elements in both subarrays are taken
  11.         if (i == left.length) {
  12.             arr[i+j] = right[j];
  13.             j++; //Left subarray was fully traversed
  14.         } else if (j == right.length) {
  15.             arr[i+j] = left[i];
  16.             i++; //Right subarray was fully traversed
  17.         } else if (left[i] <= right[j]) {
  18.             arr[i+j] = left[i];
  19.             i++; //Left element is less than Right element
  20.             //Hence, no inversion. No count increment.               
  21.         } else {
  22.             arr[i+j] = right[j];
  23.             count += left.length-i;
  24.             //Increment count with the number of inversions
  25.             j++;
  26.         }
  27.     }
  28.     return count;
  29. }
  30.  
  31.  
  32. 	static long invCount(int[] arr) {
  33.     if (arr.length < 2)
  34.         return 0;
  35.  
  36.     int m = (arr.length + 1) / 2;
  37.     //Split array into 2 subarrays. D n C.
  38.     int left[] = Arrays.copyOfRange(arr, 0, m);
  39.     int right[] = Arrays.copyOfRange(arr, m, arr.length);
  40.  
  41.     return invCount(left) + invCount(right) + merge(arr, left, right);
  42. 	}
  43.  
  44. 	public static void main (String[] args) {
  45.  
  46. 		Scanner sc  = new Scanner(System.in);
  47. 		int n = sc.nextInt(); //Input n taken
  48. 		int a[] = new int[n];
  49. 		for(int i=0;i<n;i++)
  50. 			a[i] = sc.nextInt(); //Array of integers taken
  51.  
  52. 		System.out.println(invCount(a)); //Function returns long
  53.     }
  54. } 
  55.  
Success #stdin #stdout 0.05s 711680KB
comments (?)
stdin
copy 
5
4 5 6 7 1
stdout
copy 
4
https://ideone.com/FQcFVy
5
4 5 6 7 1
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!