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

Дан массив arr[] из N целых чисел. Задача состоит в том, чтобы найти количество неупорядоченных пар (i, j) в массиве, такое, что отношение элементов с этими индексами равно отношению индексов ( arr[j] /arr[i] = j/i ).

Примеры:

Input: arr[] = {4, 5, 12, 10, 6}
Output:  2
Explaination: The pairs that follow the given condition are: 

1. (1, 3) as arr[3] / arr[1] = 12/4 = 3 = 3/1
2. (2, 4) as arr[4] / arr[2] = 10/5 = 2 = 4/2

Input: arr[] = {5, -2, 4, 20, 25, -6}
Output: 3 
 

Наивный подход : данная проблема может быть решена путем повторения всех неупорядоченных пар (i, j) в заданном массиве, при этом отслеживая количество пар, которые следуют условию arr[j]/arr[i] = j/i .

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

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

Эффективный подход: вышеуказанный подход можно оптимизировать используя наблюдение, что максимальное значение y / x для любой пары (x, y) , которое может быть достигнуто, равно N . Кроме того, у должен делиться на х . Следовательно, для x в диапазоне [1, N] выполните итерацию по всем y в диапазоне [1, N] таким образом, что y делится на x , и отслеживайте количество пар (x, y) , таких что arr[ у] / обр[х] = у / х . Это можно сделать с помощью Решета Эратосфена.

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

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