Подсчет пар индексов, у которых произведение элементов с этими индексами равно абсолютной разности индексов

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

Примеры:

Input: arr[] = {1, 1, 2, 4}
Output: 2
Explanation:
Following are the possible pairs:

1. (0, 1): The sum of these indices is 0 + 1 = 1 and the product of elements at these indices is arr[0]*arr[1] = 1*1 = 1.
2. (0, 2): The sum of these indices is 0 + 2 = 2 and the product of elements at these indices is arr[0]*arr[1] = 1*2 = 2.

Therefore, the total count of pairs is 2.

Input: arr[] = {1, 2, 1}
Output: 0

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

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, оптимизировав внутренний цикл, использованный на предыдущем шаге. Идея состоит в том, чтобы перебрать диапазон [0, N – 1] в первом цикле, а во втором цикле перейти от arr[i] – (i%arr[i]) с использованием переменной j и увеличить значение j на arr[i] до N , а затем проверьте заданные критерии. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, count как 0 , которая хранит результирующее количество пар.
• Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
  • Перебрать диапазон [arr[i] – (i%arr[i]), N], используя переменную j с шагом arr[i] и если i меньше j и arr[i]*arr[j] равно abs(i – j) , затем увеличьте значение count на 1 .
• После выполнения вышеуказанных шагов выведите в качестве результата значение count .

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

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