Подсчитайте пары из заданного массива, произведение которых находится в заданном диапазоне

Учитывая массив arr[] размера N и целые числа L и R , задача состоит в том, чтобы подсчитать количество пар [arr _i , arr _j ] , таких что i < j , и произведение arr[i] * arr[j] лежит в заданном диапазоне [L, R] , то есть L ≤ arr[i] * arr[j] ≤ R.

Примеры:

Input: arr[ ] = {4, 1, 2, 5}, L = 4, R = 9
Output: 3
Explanation: Valid pairs are {4, 1}, {1, 5} and {4, 2}.

Input: arr[ ] = {1, 2, 5, 10, 5}, L = 2, R = 15   
Output: 6
Explanation: Valid pairs are {1, 2}, {1, 5}, {1, 10}, {1, 5}, {2, 5}, {2, 5}.

Наивный подход: самый простой подход к решению проблемы — сгенерировать все возможные пары из массива и для каждой пары проверить, лежит ли ее произведение в диапазоне [L, R] или нет.

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

Эффективный подход. Эту проблему можно решить с помощью методов сортировки и бинарного поиска. Выполните следующие шаги, чтобы решить эту проблему:

• Отсортируйте массив arr[].
• Инициализируйте переменную, скажем , как 0, чтобы хранить количество пар, произведение которых лежит в диапазоне [L, R].
• Переберите диапазон [0, N-1] , используя переменную i , и выполните следующие шаги :
  • Найдите верхнюю границу элемента так, чтобы этот элемент был меньше, чем R / arr[i].
  • Найдите нижнюю границу элемента, такого, что элемент больше или равен L/arr[i].
  • Добавить верхнюю границу – нижнюю границу к ответу
• После выполнения вышеуказанных шагов напечатайте an .

Ниже приведена реализация описанного выше подхода.

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