News Leaflets
0 106

Given an array, arr[] of size N and a positive integer D, the task is to find the position i of an element in arr[] such that the prefix sum, arr[i] and suffix sum is in arithmetic progression with common difference D, i.e. arr[i] – sum(arr[0, . . ., i-1]) = sum(arr[i+1, . . ., N-1]) – arr[i] = D. If no such position exists return -1.

Examples:

Input: arr[] = { 4, 6, 20, 10, 15, 5 }, D = 10
Output: 3
Explanation:  Sum till 3rd position is 4+6 = 10.
Element at 3rd position is 20.
Suffix sum is 10 + 15 + 5 = 30.
So 10, 20, 30 is forming an AP whose common difference is 10.

Input: arr[] ={ 1, 3, 5 }, D = 7
Output: -1

Approach:  The given problem can be solved by using Linear Search approach based on the below observation:

• If the size of array is less than 3 then no sequence is possible so simply return -1.
• Calculate sum of array arr[] and store it in Sum.
• if Sum % 3 != 0, then return 0.
• Initialize a variable say Mid = Sum / 3 to store the middle element of the AP series.
• Iterate arr[] from index i = 1 to N – 2:
• Calculate the prefix sum till i-1 (say temp)
• If temp is equal to Mid – D then suffix sum is Mid + D. So return the position i+1.
• Else return -1.
• If loop terminates and no element in arr[] is equal to mid then simply return -1.

Below is the implementation of the above approach:

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `int` `checkArray(``int` `arr[], ``int` `N, ``int` `d)` `{` ` `  `    ` `    ` `    ``if` `(N < 3)` `        ``return` `-1;` ` `  `    ` `    ``int` `i, Sum = 0, temp = 0;` ` `  `    ` `    ``for` `(i = 0; i < N; i++)` `        ``Sum += arr[i];` ` `  `    ``if` `(Sum % 3 != 0)` `        ``return` `0;` ` `  `    ` `    ``int` `Mid = Sum / 3;` ` `  `    ` `    ``for` `(i = 1; i < N - 1; i++) {` ` `  `        ` `        ` `        ``temp += arr[i - 1];` ` `  `        ``if` `(arr[i] == Mid) {` ` `  `            ` `            ` `            ` `            ` `            ``if` `(temp == Mid - d)` `                ``return` `i + 1;` ` `  `            ` `            ``else` `                ``return` `0;` `        ``}` `    ``}` ` `  `    ` `    ``return` `0;` `}` ` `  `int` `main()` `{` `    ``int` `arr[] = { 4, 6, 20, 10, 15, 5 };` `    ``int` `N = ``sizeof``(arr) / ``sizeof``(arr);` `    ``int` `D = 10;` ` `  `    ` `    ``cout << checkArray(arr, N, D) << endl;` `    ``return` `0;` `}`

Time Complexity: O(N)
Auxiliary Space: O(1)