Longest subarray forming a Geometric Progression (GP)
Given a sorted array arr[] consisting of distinct numbers, the task is to find the length of the longest subarray that forms a Geometric Progression.
Examples:
Input: arr[]={1, 2, 4, 7, 14, 28, 56, 89}
Output: 4
Explanation:
The subarrays {1, 2, 4} and {7, 14, 28, 56} forms a GP.
Since {7, 14, 28, 56} is the longest, the required output is 4.Input: arr[]={3, 6, 7, 12, 24, 28, 56}
Output: 2
Naive Approach: The simplest approach to solve the problem is to generate all possible subarrays and for each subarray, check if it forms a GP or not. Keep updating the maximum length of such subarrays found. Finally, print the maximum length obtained.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by the following steps:
- Traverse the array and select a pair of adjacent elements, i.e., arr[i] and arr[i+1], as the first two terms of the Geometric Progression.
- If arr[i+1] is not divisible by arr[i], then it cannot be considered for the common ratio. Otherwise, take arr[i+1] / arr[i] as the common ratio for the current Geometric Progression.
- Increase and store the length of the Geometric Progression if the subsequent elements have the same common ratio. Otherwise, update the common ratio equal to the ratio of the new pair of adjacent elements.
- Finally, return the length of the longest subarray that forms a Geometric Progression as the output.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to return the length of // the longest subarray forming a // GP in a sorted array int longestGP( int A[], int N) { // Base Case if (N < 2) return N; // Stores the length of GP // and the common ratio int length = 1, common_ratio = 1; // Stores the maximum // length of the GP int maxlength = 1; // Traverse the array for ( int i = 0; i < N - 1; i++) { // Check if the common ratio // is valid for GP if (A[i + 1] % A[i] == 0) { // If the current common ratio // is equal to previous common ratio if (A[i + 1] / A[i] == common_ratio) { // Increment the length of the GP length = length + 1; // Store the max length of GP maxlength = max(maxlength, length); } // Otherwise else { // Update the common ratio common_ratio = A[i + 1] / A[i]; // Update the length of GP length = 2; } } else { // Store the max length of GP maxlength = max(maxlength, length); // Update the length of GP length = 1; } } // Store the max length of GP maxlength = max(maxlength, length); // Return the max length of GP return maxlength; } // Driver Code int main() { // Given array int arr[] = { 1, 2, 4, 7, 14, 28, 56, 89 }; // Length of the array int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << longestGP(arr, N); return 0; } |
Java
// Java program to implement // the above approach import java.io.*; class GFG{ // Function to return the length of // the longest subarray forming a // GP in a sorted array static int longestGP( int A[], int N) { // Base Case if (N < 2 ) return N; // Stores the length of GP // and the common ratio int length = 1 , common_ratio = 1 ; // Stores the maximum // length of the GP int maxlength = 1 ; // Traverse the array for ( int i = 0 ; i < N - 1 ; i++) { // Check if the common ratio // is valid for GP if (A[i + 1 ] % A[i] == 0 ) { // If the current common ratio // is equal to previous common ratio if (A[i + 1 ] / A[i] == common_ratio) { // Increment the length of the GP length = length + 1 ; // Store the max length of GP maxlength = Math.max(maxlength, length); } // Otherwise else { // Update the common ratio common_ratio = A[i + 1 ] / A[i]; // Update the length of GP length = 2 ; } } else { // Store the max length of GP maxlength = Math.max(maxlength, length); // Update the length of GP length = 1 ; } } // Store the max length of GP maxlength = Math.max(maxlength, length); // Return the max length of GP return maxlength; } // Driver code public static void main (String[] args) { // Given array int arr[] = { 1 , 2 , 4 , 7 , 14 , 28 , 56 , 89 }; // Length of the array int N = arr.length; // Function call System.out.println(longestGP(arr, N)); } } // This code is contributed by jana_sayantan |
Python3
# Python3 program to implement # the above approach # Function to return the length of # the longest subarray forming a # GP in a sorted array def longestGP(A, N): # Base Case if (N < 2 ): return N # Stores the length of GP # and the common ratio length = 1 common_ratio = 1 # Stores the maximum # length of the GP maxlength = 1 # Traverse the array for i in range (N - 1 ): # Check if the common ratio # is valid for GP if (A[i + 1 ] % A[i] = = 0 ): # If the current common ratio # is equal to previous common ratio if (A[i + 1 ] / / A[i] = = common_ratio): # Increment the length of the GP length = length + 1 # Store the max length of GP maxlength = max (maxlength, length) # Otherwise else : # Update the common ratio common_ratio = A[i + 1 ] / / A[i] # Update the length of GP length = 2 else : # Store the max length of GP maxlength = max (maxlength, length) # Update the length of GP length = 1 # Store the max length of GP maxlength = max (maxlength, length) # Return the max length of GP return maxlength # Driver Code # Given array arr = [ 1 , 2 , 4 , 7 , 14 , 28 , 56 , 89 ] # Length of the array N = len (arr) # Function call print (longestGP(arr, N)) # This code is contributed by sanjoy_62 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to return the length of // the longest subarray forming a // GP in a sorted array static int longestGP( int []A, int N) { // Base Case if (N < 2) return N; // Stores the length of GP // and the common ratio int length = 1, common_ratio = 1; // Stores the maximum // length of the GP int maxlength = 1; // Traverse the array for ( int i = 0; i < N - 1; i++) { // Check if the common ratio // is valid for GP if (A[i + 1] % A[i] == 0) { // If the current common ratio // is equal to previous common ratio if (A[i + 1] / A[i] == common_ratio) { // Increment the length of the GP length = length + 1; // Store the max length of GP maxlength = Math.Max(maxlength, length); } // Otherwise else { // Update the common ratio common_ratio = A[i + 1] / A[i]; // Update the length of GP length = 2; } } else { // Store the max length of GP maxlength = Math.Max(maxlength, length); // Update the length of GP length = 1; } } // Store the max length of GP maxlength = Math.Max(maxlength, length); // Return the max length of GP return maxlength; } // Driver code public static void Main(String[] args) { // Given array int []arr = {1, 2, 4, 7, 14, 28, 56, 89}; // Length of the array int N = arr.Length; // Function call Console.WriteLine(longestGP(arr, N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript implementation of the above approach // Function to return the length of // the longest subarray forming a // GP in a sorted array function longestGP(A, N) { // Base Case if (N < 2) return N; // Stores the length of GP // and the common ratio let length = 1, common_ratio = 1; // Stores the maximum // length of the GP let maxlength = 1; // Traverse the array for (let i = 0; i < N - 1; i++) { // Check if the common ratio // is valid for GP if (A[i + 1] % A[i] == 0) { // If the current common ratio // is equal to previous common ratio if (A[i + 1] / A[i] == common_ratio) { // Increment the length of the GP length = length + 1; // Store the max length of GP maxlength = Math.max(maxlength, length); } // Otherwise else { // Update the common ratio common_ratio = A[i + 1] / A[i]; // Update the length of GP length = 2; } } else { // Store the max length of GP maxlength = Math.max(maxlength, length); // Update the length of GP length = 1; } } // Store the max length of GP maxlength = Math.max(maxlength, length); // Return the max length of GP return maxlength; } // Driver code // Given array let arr = [ 1, 2, 4, 7, 14, 28, 56, 89 ]; // Length of the array let N = arr.length; // Function call document.write(longestGP(arr, N)); // This code is contributed by code_hunt. </script> |
4
Time Complexity: O(N)
Space Complexity: O(1)