Найдите элемент массива, имеющий равную сумму простых чисел слева и справа

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти индекс в данном массиве, где сумма простых чисел слева от него равна сумме простых чисел справа от него.

Примеры:

Input: arr[] = {11, 4, 7, 6, 13, 1, 5}
Output: 3
Explanation: Sum of prime numbers to left of index 3 = 11 + 7 = 18
Sum of prime numbers to right of index 3 = 13 + 5 = 18

Input: arr[] = {5, 2, 1, 7}
Output: 2
Explanation: Sum of prime numbers to left of index 2 = 5 + 2 = 7
Sum of prime numbers to right of index 2 = 7

Наивный подход: самый простой подход — пройтись по массиву и проверить заданное условие для каждого индекса в диапазоне [0, N — 1] . Если условие выполняется для любого индекса, выведите значение этого индекса.

Временная сложность: O(N ² *√M), где M — самый большой элемент в массиве.
Вспомогательное пространство: O(1)

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

• Пройдите через массив, чтобы найти максимальное значение, присутствующее в массиве.
• Используйте Решето Эратосфена, чтобы найти простые числа, которые меньше или равны максимальному значению, присутствующему в массиве. Сохраните эти элементы на карте.
• Инициализируйте массив, скажем, first_array . Пройдите массив и сохраните сумму всех простых чисел до i ^-го индекса в first_array[i] .
• Инициализируйте массив, скажем, second_array . Пройдите массив в обратном порядке и сохраните сумму всех элементов до i ^-го индекса в second_array[i] .
• Пройдитесь по массивам first_array и second_array и проверьте, равны ли по любому индексу оба их значения или нет. Если окажется, что это правда, верните этот индекс.

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

Временная сложность: O(N + max(arr[])loglog(max(arr[]))
Вспомогательное пространство: O(max(arr[]) + N)