Подсчитайте максимальное количество непересекающихся пар, один элемент которых не менее чем в K раз превышает другой.

Учитывая массив arr[] и положительное целое число K , задача состоит в том, чтобы найти максимальное количество непересекающихся пар (arr[i], arr[j]) , таких что arr[j] ≥ K * arr[i] .

Примеры:

Input: arr[] = { 1, 9, 4, 7, 3 }, K = 2
Output: 2
Explanation:
There can be 2 possible pairs that can formed from the given array i.e., (4, 1) and (7, 3) that satisfy the given conditions.

Input: arr[] = {2, 3, 4, 5, 6, 7, 8, 9}, K = 3
Output: 2

Подход: Данная проблема может быть решена с использованием подхода с двумя указателями. Выполните следующие шаги, чтобы решить данную проблему:

1. Отсортируйте заданный массив в порядке возрастания.
2. Инициализируйте две переменные i и j как 0 и (N / 2) соответственно и переменную count , которая хранит результирующее максимальное количество пар.
3. Пройдите по заданному массиву в диапазоне [0, N/2] и выполните следующие шаги:
   • Увеличивайте значение j до тех пор, пока j < N и arr[j] < K * arr[i] .
   • Если значение j меньше, чем N , то увеличьте количество пар на 1 .
   • Увеличьте значение j на 1 .
4. После выполнения вышеуказанных шагов выведите в качестве результата значение count .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)