- Arrays, Geometric Progression, Mathematical, Pattern Searching, prefix-sum, suffix-sum

Find position i to split Array such that prefix sum till i-1, i and suffix sum till i+1 are in GP with common ratio K

Given an array, arr[] and a positive integer K. The task is to find the position say i of the element in arr[] such that prefix sum till i-1, i and suffix sum till i+1 are in Geometric Progression with common ratio K. Examples:Input: arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 }, K = 2Output: 4Explanation:  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 Approach:  The given problem can be solved by using Linear Search and basic prefix sum. Follow the steps below to solve the given problem.If the size of array is less than 3 then no sequence is possible so simply return -1.Initialize a variable say, arrSum to store sum of all elements of arr[].Calculate sum of array arr[] and store it in arrSum.if arrSum % R != 0, then return 0. Where R = K * K + 1 + K + 1.Initialize a variable say mid = K * (Sum / R) to store middle element of GP series with common ratio as K.Take a variable say temp to store temporary results.Iterate arr[] from index i to (size of arr[]) – 2 with variable i.tem = tem + arr[i-1]if arr[i] = midif tem = mid/k, return (i+1) as the answer.else return 0.If loop terminates and no element in arr[] is equal to mid then simply return 0.Below is the implementation of the above approach:C++#include using namespace std;int checkArray(int arr[], int N, int k){            if (N < 3)        return -1;        int i, Sum = 0, temp = 0;        for (i = 0; i < N; i++)        Sum += arr[i];    int R = (k * k + k + 1);    if (Sum % R != 0)        return 0;        int Mid = k * (Sum / R);        for (i = 1; i < N - 1; i++) {                        temp += arr[i - 1];        if (arr[i] == Mid) {                                                if (temp == Mid / k)                return i + 1;                        else                return 0;        }    }        return 0;}int main(){        int arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 };    int N = sizeof(arr) / sizeof(arr[0]);    int K = 2;    cout