Longest subarray forming a Geometric Progression in java
Longest subarray forming a Geometric Progression refers to finding the maximum length of a contiguous subarray within the given array such that the elements of the subarray form a Geometric Progression.
Example:
Input: arr[]={3, 9, 27, 81, 243}
Output: 5
Explanation: The entire array forms a GP with a common ratio of 3 (each term is obtained by multiplying the previous term by 3). Hence, the length of the longest subarray forming a GP is 5, which is the length of the entire array.
Brute Force Approach
Algorithm
Step 1: Initialize maxLength to 0.
Step 2: Iterate through each potential starting point of the subarray using a loop.
Step 3: Within the loop, use another loop to explore all possible subarrays starting from the current starting point.
Step 4: Check if each explored subarray forms a Geometric Progression by ensuring the ratio between consecutive elements remains consistent.
Step 5: If a subarray forms a GP and its length exceeds the current maxLength, update maxLength accordingly.
Step 6: After exploring all subarrays, return the final maxLength, representing the length of the longest subarray forming a GP.
FileName: SubarrayGP.java
public class SubarrayGP { public static int longestSubarrayGP(int[] arr) { int maxLength = 0; // Initialize maxLength to 0 // Loop through each element in the array as the potential starting point of the subarray for (int i = 0; i < arr.length; i++) { // Try all subarrays starting from index i for (int j = i; j < arr.length; j++) { // Check if the subarray from index i to j forms a GP if (isGeometricProgression(arr, i, j)) { // Update maxLength if the length of the current subarray is greater maxLength = Math.max(maxLength, j - i + 1); } } } return maxLength; } private static boolean isGeometricProgression(int[] arr, int start, int end) { if (end - start < 2) return true; int ratio = arr[start + 1] / arr[start]; // Calculate the common ratio // Check if each element in the subarray has the same ratio with its previous element for (int i = start + 1; i <= end; i++) { if (arr[i] / arr[i - 1] != ratio) { return false; } } return true; } public static void main(String[] args) { int[] arr = {3, 9, 27, 81, 243}; System.out.println(longestSubarrayGP(arr)); } }
Output:
5
Complexity Analysis: The time complexity of the code is O(n^3) due to nested loops iterating through each possible subarray, where n is the length of the input array. The space complexity is O(1) as it only requires a constant amount of additional memory for variables regardless of the input size.
Sliding Window Approach
Algorithm
Step 1: Start with initializing variables maxLength, start, and end to 0.
Step 2: Iterate through the array while end is less than the array length.
Step 3: Check if the current subarray from index start to end forms a Geometric Progression.
Step 4: If the subarray is a GP and its length exceeds the current maxLength, update maxLength.
Step 5: Move the pointers (start and end) accordingly based on the GP condition.
Step 6: Return the maximum length found, representing the longest subarray forming a GP.
FileName: SubarrayGP1.java
public class SubarrayGP1 { public static int longestSubarrayGP(int[] arr) { int maxLength = 0; int start = 0; int end = 0; while (end < arr.length) { // If the current subarray is a GP if (isGeometricProgression(arr, start, end)) { // Update maxLength maxLength = Math.max(maxLength, end - start + 1); end++; // Move end pointer to the next element } else { start++; // Move start pointer to the next element if (start > end) { // Ensure end pointer doesn't lag behind start pointer end = start; } } } return maxLength; } private static boolean isGeometricProgression(int[] arr, int start, int end) { if (end - start < 2) return true; // Single or two elements always form a GP int ratio = arr[start + 1] / arr[start]; // Calculate the common ratio // Check if each element in the subarray has the same ratio with its previous element for (int i = start + 1; i <= end; i++) { if (arr[i] / arr[i - 1] != ratio) { return false; } } return true; } public static void main(String[] args) { int[] arr = {3, 9, 27, 81, 243}; System.out.println(longestSubarrayGP(arr)); } }
Output:
5
Complexity Analysis: The time complexity of the code is O(n), where n is the length of the input array, due to iterating through the array once. The space complexity is O(1) as the algorithm uses a constant amount of extra space regardless of the input size.