Количество пар в заданном массиве с произведением их значений, равным сумме их индексов (arr[i]*arr[j] = i+j)

Опубликовано: 21 Сентября, 2022

Дан массив arr[] длины N с различными целыми числами от 1 до 2*N. Задача состоит в том, чтобы подсчитать количество пар индексов (i, j) , таких что (i < j) и arr[i] * arr[ j] = i + j , т.е. вычислить количество пар, произведение которых равно сумме их индексов.

Примеры:

Input: N = 5, arr[] = {3, 1, 5, 9, 2}
Output: 3
Explanation: There are three pairs (i, j) such that (i < j) and arr[i] * arr[j] = i + j (1, 2), (1, 5), (2, 3)

Input: N = 3, arr[] = {6, 1, 5}
Output: 1

Наивный подход: перебрать все пары индексов (i, j) с (i < j) и проверить для каждой пары, выполняется ли вышеуказанное условие, затем увеличить ответ на 1, в противном случае перейти к следующей паре.

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

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

Эффективный подход: перепишите упомянутое условие как

arr[j] = (i + j)/arr[i]


Следовательно, для каждого кратного arr[i] найдите соответствующий j и проверьте, равен ли arr[j] (i + j)/arr[i]. Этот подход эффективен, потому что для каждого i требуется пройти через каждое кратное i до 2*N . Поскольку все числа в массиве различны , можно сделать вывод, что общее количество итераций для вычисления j будет таким:

N + N/2 + N/3 + N/4 + N/5…… 

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

  • Инициализируйте переменную ans как 0 , чтобы сохранить ответ.
  • Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
    • Инициализируйте переменную k как значение arr[i].
    • Повторяйте цикл while, пока k не станет меньше 2*N , и выполните следующие задачи:
      • Инициализируйте переменную j как ki-1.
      • Если j больше, чем равно 1 , и меньше, чем равно N , а arr[j – 1] равно k / arr[i] и j больше i+1, то увеличьте значение ans на 1.
  • После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ