Question

Write in Java. Program need to have runtimes < n^2 to satisfy the runtime efficiency of some of the testsets.

Question 2: Understanding Orders

Given an array A of size N, find the number of ordered pairs (i, j) such that i < j and A[i] < A[j].

Input:

• First line contains one integer, N, size of array.

• Second line contains N space separated integers denoting the elements of the array A.

Output:

Print the total number of ordered pairs (i, j) such that i < j and A[i] < A[j].

Constraints:

1. 1 ? N ? 10^6

2. ?105 ? A[i] ? 106

Input

5

4 1 3 2 5

output

6

The 6 cases are: 4 < 5, 1 < 3, 1 < 2, 1 < 5, 3 < 5, 2 < 5.

Answer 1

//TestCode.java

import java.util.Scanner;

public class TestCode {
    public static void main(String args[]){
        int n, count = 0;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int arr[] = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++){
                if(arr[i] < arr[j]){
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}