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 = 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
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 1 to (size of arr[]) – 2 with variable i.
- temp = temp + arr[i-1]
- if arr[i] = mid
- if temp = 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++
// C++ program for the above approach#include <iostream>using namespace std;// Function to check if there is// an element forming G.P. series// having common ratio kint checkArray(int arr[], int N, int k){ // 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]; int R = (k * k + k + 1); if (Sum % R != 0) return 0; // Calculate Middle element of G.P. series int Mid = k * (Sum / R); // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of G.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the G.P. series if the first // element is in G.P. of common ratio k if (temp == Mid / k) return i + 1; // Else return 0 else return 0; } } // if middle element is not found in arr[] return 0;}// Driver Codeint main(){ // Given array int arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 2; cout << checkArray(arr, N, K) << endl; return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to check if there is// an element forming G.P. series// having common ratio kstatic int checkArray(int arr[], int N, int k){ // 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]; int R = (k * k + k + 1); if (Sum % R != 0) return 0; // Calculate Middle element of G.P. series int Mid = k * (Sum / R); // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of G.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the G.P. series if the first // element is in G.P. of common ratio k if (temp == Mid / k) return i + 1; // Else return 0 else return 0; } } // if middle element is not found in arr[] return 0;}// Driver Codepublic static void main (String[] args) { // Given array int arr[] = { 5, 1, 4, 20, 6, 15, 9, 10 }; int N = arr.length; int K = 2; System.out.println(checkArray(arr, N, K));}}// This code is contributed by Dharanendra L V. |
Python3
# python program for the above approach# Function to check if there is# an element forming G.P. series# having common ratio kdef checkArray(arr, N, k): # If size of array is less than # three then return -1 if (N < 3): return -1 # Initialize the variables Sum = 0 temp = 0 # Calculate total sum of array for i in range(0, N): Sum += arr[i] R = (k * k + k + 1) if (Sum % R != 0): return 0 # Calculate Middle element of G.P. series Mid = k * (Sum // R) # Iterate over the range for i in range(1, N-1): # Store the first element of G.P. # series in the variable temp temp += arr[i - 1] if (arr[i] == Mid): # Return position of middle element # of the G.P. series if the first # element is in G.P. of common ratio k if (temp == Mid // k): return i + 1 # Else return 0 else: return 0 # if middle element is not found in arr[] return 0# Driver Codeif __name__ == "__main__": # Given array arr = [5, 1, 4, 20, 6, 15, 9, 10] N = len(arr) K = 2 print(checkArray(arr, N, K)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;class GFG { // Function to check if there is // an element forming G.P. series // having common ratio k static int checkArray(int[] arr, int N, int k) { // 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]; int R = (k * k + k + 1); if (Sum % R != 0) return 0; // Calculate Middle element of G.P. series int Mid = k * (Sum / R); // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of G.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the G.P. series if the first // element is in G.P. of common ratio k if (temp == Mid / k) 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) { // Given array int[] arr = { 5, 1, 4, 20, 6, 15, 9, 10 }; int N = arr.Length; int K = 2; Console.WriteLine(checkArray(arr, N, K)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if there is // an element forming G.P. series // having common ratio k function checkArray(arr, N, k) { // 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]; let R = (k * k + k + 1); if (Sum % R != 0) return 0; // Calculate Middle element of G.P. series let Mid = k * (Sum / R); // Iterate over the range for (i = 1; i < N - 1; i++) { // Store the first element of G.P. // series in the variable temp temp += arr[i - 1]; if (arr[i] == Mid) { // Return position of middle element // of the G.P. series if the first // element is in G.P. of common ratio k if (temp == Mid / k) return i + 1; // Else return 0 else return 0; } } // if middle element is not found in arr[] return 0; } // Driver Code // Given array let arr = [5, 1, 4, 20, 6, 15, 9, 10]; let N = arr.length; let K = 2; document.write(checkArray(arr, N, K) + "<br>");// This code is contributed by Potta Lokesh </script> |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
