Подсчитайте все возможные пары в заданном массиве с продуктом K

Дан целочисленный массив arr[] размера N и положительное целое число K , задача состоит в том, чтобы посчитать все пары в массиве с произведением, равным K .

Примеры:

Input: arr[] = {1, 2, 16, 4, 4, 4, 8 }, K=16
Output: 5
Explanation: Possible pairs are (1, 16), (2, 8), (4, 4), (4, 4), (4, 4)

Input: arr[] = {1, 10, 20, 10, 4, 5, 5, 2 }, K=20
Output: 5
Explanation: Possible pairs are (1, 20), (2, 10), (2, 10), (4, 5), (4, 5)

Подход: Идея состоит в том, чтобы использовать хеширование для хранения элементов и проверки, существует ли K/arr[i] в массиве или не использует карту, и соответственно увеличить количество.

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную count как 0 , чтобы сохранить ответ.
• Инициализируйте unordered_map<int, int> mp[] .
• Перебрать диапазон [0, N) с помощью переменной i и сохранить частоты всех элементов массива arr[] в карте mp[].
• Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
  • Инициализируйте индекс переменной как K/arr[i] .
  • Если K не является степенью числа 2 , а index присутствует в карте mp[] , то увеличьте значение count на mp[arr[i]]*mp[index] и сотрите их оба с карты mp[].
  • Если K является степенью числа 2 , а index присутствует в карте mp[] , то увеличьте значение count на mp[index]*(mp[index]-1)/2 и сотрите его с карты mp[].
• После выполнения вышеуказанных шагов выведите значение count в качестве ответа.

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

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