Count number of pair such that (Max/min) is less than 2 in Array

Given an array arr[] of size N (0 < arr[i] < 10⁶), the task is to find the total count of pairs such that by dividing the largest number by the smallest number of the pair, the result is < 2.

Examples:

Input: arr[ ] = { 3, 12, 5, 13 }
Output: 2
Explanation: 
The two such pairs are (3, 5) and (12, 13).

Input: arr[ ] = { 2, 3, 9, 5 }
Output: 3

Naive Approach:

The simplest approach to solve this problem is to generate all possible pairs, and check for each pair such that by dividing the largest number by the smallest number of the pair, the result is < 2.

Time Complexity: O(n²)
Auxiliary Space: O(1)

Efficient Approach:

Follow the steps below to solve the problem:

Sort the array in increasing order.
Use the two-pointer technique to have a low and high index, i.e. variable low and i.
If arr[i] becomes >= (arr[low] * 2), it means that all the numbers between low and i are less than (arr[low] * 2).
To get these elements, use the formula i – low – 1, and update the result, i.e, res.

Below is the implementation of the above approach:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to find the total count of pairs such
// that by dividing the largest number by the
// smallest number of the pair, the result is < 2.
int divisiblePairs(int arr[], int N)
{
    int res = 0, low = 0;

    // Traverse the array
    for (int i = 1; i < N - 1; i++) {
        if (i == low)
            continue;
        if (arr[i] >= (arr[low] * 2)) {
            res += i - low - 1;
            low++;
            i--;
        }
    }

    // Checking with the last element of the array
    while (low != N - 1) {
        if (arr[N - 1] < (arr[low] * 2))
            res += N - 1 - low;
        else
            res += N - 1 - low - 1;
        low++;
    }

    return res;
}

// Driver Code
int main()
{

    int arr[] = { 3, 12, 5, 13 };

    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);

    // Sort the array
    sort(arr, arr + N);

    cout << divisiblePairs(arr, N);
    return 0;
}

Output:

Time Complexity: O(nlogn)
Auxiliary Space: O(1)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.