Количество различных пар, один элемент которых в K раз больше другого

Учитывая массив arr[] и целое число K, найдите максимальное количество пар, которые можно составить так, чтобы один элемент был в K раз больше другого, т. е. arr[i]=K*arr[j] .

Примеры:

Input: arr[] = {1, 2, 1, 2, 4} K = 2
Output: 2
Explanation: There are two possible ways to construct pairs: ({1, 2}, {1, 2}) and ({1, 2}, {2, 4}).

Input: a = {5, 4, 3, 2, 1} K = 2
Output: 1
Explanation: We can construct either set {1, 2} or set {2, 4}.

Подход: отсортируйте данный массив arr[] и проверьте все возможные пары массива arr[] и проверьте, является ли данный (i, j) arr[i]=2*arr[j]. Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте массив arr[] с помощью функции sort в C++ STL.
• Инициализируйте вектор, используемый для подсчета уже используемых элементов.
• Инициализируйте переменную ans как 0 , чтобы сохранить количество всех возможных пар.
• Переберите диапазон [0, N-1], используя переменную i , и выполните следующие шаги:
  • Перебрать диапазон [l, N-1], используя переменную j , и сделать следующее:
    • Если значение used[j] и used[i] равно false и arr[j]=K*arr[i] , тогда установите значение used[i] и used[j] равным true и увеличьте значение на 1 и разорвать цикл .
• Наконец, после выполнения вышеуказанных шагов выведите значение ans.

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

Временная сложность: O(N^2)
Космическая сложность: O(N)