Find position forming AP with prefix and suffix sum of Array with common difference D

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:

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