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:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if there is // an element forming A.P. series // having common difference d int checkArray( int arr[], int N, int d) { // If size of array is less than // three then return -1 if (N < 3) return -1; // Initialize the variables int i, Sum = 0, temp = 0; // Calculate total sum of array for (i = 0; i < N; i++) Sum += arr[i]; if (Sum % 3 != 0) return 0; // Calculate Middle element of A.P. series int Mid = Sum / 3; // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of A.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the A.P. series if the first // element is in A.P. with middle element // having common difference d if (temp == Mid - d) return i + 1; // Else return 0 else return 0; } } // If middle element is not found in arr[] return 0; } // Driver Code int main() { int arr[] = { 4, 6, 20, 10, 15, 5 }; int N = sizeof (arr) / sizeof (arr[0]); int D = 10; // Function call cout << checkArray(arr, N, D) << endl; return 0; } |
Java
// JAVA program for the above approach import java.util.*; class GFG { // Function to check if there is // an element forming A.P. series // having common difference d public static int checkArray( int arr[], int N, int d) { // If size of array is less than // three then return -1 if (N < 3 ) return - 1 ; // Initialize the variables int i, Sum = 0 , temp = 0 ; // Calculate total sum of array for (i = 0 ; i < N; i++) Sum += arr[i]; if (Sum % 3 != 0 ) return 0 ; // Calculate Middle element of A.P. series int Mid = Sum / 3 ; // Iterate over the range for (i = 1 ; i < N - 1 ; i++) { // Store the first element of A.P. // series in the variable temp temp += arr[i - 1 ]; if (arr[i] == Mid) { // Return position of middle element // of the A.P. series if the first // element is in A.P. with middle element // having common difference d if (temp == Mid - d) return i + 1 ; // Else return 0 else return 0 ; } } // If middle element is not found in arr[] return 0 ; } // Driver Code public static void main(String[] args) { int arr[] = { 4 , 6 , 20 , 10 , 15 , 5 }; int N = arr.length; int D = 10 ; // Function call System.out.println(checkArray(arr, N, D)); } } // This code is contributed by Taranpreet |
Python3
#Python program for the above approach # Function to check if there is # an element forming A.P. series # having common difference d def checkArray(arr, N, d): # If size of array is less than # three then return -1 if (N < 3 ): return - 1 # Initialize the variables i = 0 Sum = 0 temp = 0 # Calculate total sum of array for i in range (N): Sum + = arr[i] if ( Sum % 3 ! = 0 ): return 0 # Calculate Middle element of A.P. series Mid = Sum / 3 # Iterate over the range for i in range ( 1 , N - 1 ): # Store the first element of A.P. # series in the variable temp temp + = arr[i - 1 ] if (arr[i] = = Mid): # Return position of middle element # of the A.P. series if the first # element is in A.P. with middle element # having common difference d if (temp = = Mid - d): return i + 1 # Else return 0 else : return 0 # If middle element is not found in arr[] return 0 # Driver Code if __name__ = = "__main__" : arr = [ 4 , 6 , 20 , 10 , 15 , 5 ] N = len (arr) D = 10 # Function call print (checkArray(arr, N, D)) # This code is contributed by hrithikgarg03188. |
C#
// C# program for the above approach using System; class GFG { // Function to check if there is // an element forming A.P. series // having common difference d static int checkArray( int []arr, int N, int d) { // If size of array is less than // three then return -1 if (N < 3) return -1; // Initialize the variables int i, Sum = 0, temp = 0; // Calculate total sum of array for (i = 0; i < N; i++) Sum += arr[i]; if (Sum % 3 != 0) return 0; // Calculate Middle element of A.P. series int Mid = Sum / 3; // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of A.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the A.P. series if the first // element is in A.P. with middle element // having common difference d if (temp == Mid - d) return i + 1; // Else return 0 else return 0; } } // If middle element is not found in arr[] return 0; } // Driver Code public static void Main() { int []arr = { 4, 6, 20, 10, 15, 5 }; int N = arr.Length; int D = 10; // Function call Console.WriteLine(checkArray(arr, N, D)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for the above approach // Function to check if there is // an element forming A.P. series // having common difference d const checkArray = (arr, N, d) => { // If size of array is less than // three then return -1 if (N < 3) return -1; // Initialize the variables let i, Sum = 0, temp = 0; // Calculate total sum of array for (i = 0; i < N; i++) Sum += arr[i]; if (Sum % 3 != 0) return 0; // Calculate Middle element of A.P. series let Mid = parseInt(Sum / 3); // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of A.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the A.P. series if the first // element is in A.P. with middle element // having common difference d if (temp == Mid - d) return i + 1; // Else return 0 else return 0; } } // If middle element is not found in arr[] return 0; } // Driver Code let arr = [4, 6, 20, 10, 15, 5]; let N = arr.length; let D = 10; // Function call document.write(checkArray(arr, N, D)); // This code is contributed by rakeshsahni </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us