✅K-Pairs (Contest)

K-Pairs (Contest) medium Time Limit: 2 sec Memory Limit: 128000 kB

Problem Statement :

Given an array A of size N and an integer K, find and print the number of pairs of indices i, j (1 <= i < j <= N) such that Ai * Aj > K. Input First line of the input contains two integers N and K. The second line of the input contains N space seperated integers.

Constraints: 1 <= N <= 105 1 <= K <= 1012 1 <= Ai <= 106 Output Print the number of pairs of indices i, j (1 <= i < j <= N) such that Ai * Aj > K. Example Sample Input: 7 20 5 7 2 3 2 9 1

Sample Output: 5

Explanation: The following pairs of indices satisfy the condition (1-based indexing) (1, 2) -> 5 * 7 = 35 (1, 6) -> 5 * 9 = 45 (2, 4) -> 7 * 3 = 21 (2, 6) -> 7 * 9 = 63 (4, 6) -> 3 * 9 = 27 All these products are greater than K (= 20).

link:https://my.newtonschool.co/playground/code/kof605kbyshx/

```java
import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
        // Your code here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] arr = new long[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextLong();
        }

        Arrays.sort(arr);

        long count = 0;
        int i = 0;
        int j = n-1;

        while(i < j){
            if(arr[i]*arr[j] <= k){
                i++;
            } else{
                count += (j-i);
                j--;
            }
        }

        System.out.print(count);
        
    }
}
```