Найдите позицию i для разделения массива так, чтобы сумма префиксов до i-1, i и сумма суффиксов до i+1 находились в GP с общим отношением K

Дан массив, arr[] и положительное целое число K . Задача состоит в том, чтобы найти позицию say i элемента в arr[] такую, что сумма префиксов до i-1 , i и сумма суффиксов до i+1 находятся в геометрической прогрессии с обыкновенным отношением K .

Примеры :

Input: arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 }, K = 2
Output: 4
Explanation:  The following operations are performed to get required GP.
Sum of element from position 1 to 3 is 5 + 1 + 4 = 10 and from 5 to 8 is 6 + 15 + 9 + 10 = 40.
And element at position 4 is 20.
Therefore10, 20, 40 is a Geometric Progression series with common ratio K.

Input: arr[] ={ -3, 5, 0, 2, 1, 25, 25, 100 }, K = 5 
Output: 6 

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

• Если размер массива меньше 3, то никакая последовательность невозможна, поэтому просто верните -1.
• Инициализируйте переменную, скажем, arrSum для хранения суммы всех элементов arr[] .
• Вычислите сумму массива arr[] и сохраните ее в arrSum .
• если arrSum % R != 0 , то вернуть 0 . Где R = К * К + 1 + К + 1 .
• Инициализируйте переменную, скажем, mid = K * (Sum / R) , чтобы сохранить средний элемент ряда GP с общим отношением как K.
• Возьмите переменную, скажем, temp для хранения временных результатов.
• Итерировать arr[] от индекса 1 до ( размер arr[]) – 2 с переменной i .
  • темп = темп + обр[i-1]
  • если обр[i] = середина
    • если temp = mid/k , вернуть (i+1) в качестве ответа.
    • иначе вернуть 0 .
• Если цикл завершается и ни один элемент в arr[] не равен mid, просто верните 0 .

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

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