Count subarrays of atleast size 3 forming a Geometric Progression (GP)
Given an array arr[] of N integers, the task is to find the count of all subarrays from the given array of at least size 3 forming a Geometric Progression.
Examples:
Input: arr[] = {1, 2, 4, 8}
Output: 3
Explanation: The required subarrays forming geometric progression are:
- {1, 2, 4}
- {2, 4, 8}
- {1, 2, 4, 8}
Input: arr[] = {1, 2, 4, 8, 16, 24}
Output: 6
Explanation: The required subarrays forming geometric progression are:
- {1, 2, 4}
- {2, 4, 8}
- {4, 8, 16}
- {1, 2, 4, 8}
- {2, 4, 8, 16}
- {1, 2, 4, 8, 16}
Naive Approach: The simplest approach is to generate all the subarrays of size at least 3 and count all those subarrays forming a Geometric Progression. Print the count after checking all the subarrays.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The idea is to use a property of Geometric Progression i.e., {a, b, c} is GP if and only if a*c = b. Follow the below steps to solve the problem:
- Initialize a variable, res, and count with 0 to store the total subarrays forming geometric progression and length of the current subarray.
- Traverse the given array over the range [2, N – 1] and increment the value of count if the current element forming a geometric progression i.e., arr[i]*arr[i – 2] = arr[i – 1]*arr[i – 1] Otherwise, set count as zero.
- Add count to res for each iteration in the above steps.
- After the above steps, print the value of res as the resultant count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count all the subarrays // of size at least 3 forming GP int numberOfGP( int L[], int N) { // If array size is less than 3 if (N <= 2) return 0; // Stores the count of subarray int count = 0; // Stores the count of subarray // for each iteration int res = 0; // Traverse the array for ( int i = 2; i < N; ++i) { // Check if L[i] forms GP if (L[i - 1] * L[i - 1] == L[i] * L[i - 2]) { ++count; } // Otherwise, update count to 0 else { count = 0; } // Update the final count res += count; } // Return the final count return res; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 4, 8, 16, 24 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << numberOfGP(arr, N); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function to count all // the subarrays of size // at least 3 forming GP static int numberOfGP( int L[], int N) { // If array size // is less than 3 if (N <= 2 ) return 0 ; // Stores the count // of subarray int count = 0 ; // Stores the count // of subarray for // each iteration int res = 0 ; // Traverse the array for ( int i = 2 ; i < N; ++i) { // Check if L[i] forms GP if (L[i - 1 ] * L[i - 1 ] == L[i] * L[i - 2 ]) { ++count; } // Otherwise, update // count to 0 else { count = 0 ; } // Update the // final count res += count; } // Return the final count return res; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 4 , 8 , 16 , 24 }; int N = arr.length; // Function Call System.out.print(numberOfGP(arr, N)); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach # Function to count all the subarrays # of size at least 3 forming GP def numberOfGP(L, N): # If array size is less than 3 if (N < = 2 ): return 0 # Stores the count of subarray count = 0 # Stores the count of subarray # for each iteration res = 0 # Traverse the array for i in range ( 2 , N): # Check if L[i] forms GP if (L[i - 1 ] * L[i - 1 ] = = L[i] * L[i - 2 ]): count + = 1 # Otherwise, update count to 0 else : count = 0 # Update the final count res + = count # Return the final count return res # Driver Code if __name__ = = '__main__' : # Given array arr[] arr = [ 1 , 2 , 4 , 8 , 16 , 24 ] N = len (arr) # Function Call print (numberOfGP(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; class GFG { // Function to count all // the subarrays of size // at least 3 forming GP static int numberOfGP( int [] L, int N) { // If array size // is less than 3 if (N <= 2) return 0; // Stores the count // of subarray int count = 0; // Stores the count // of subarray for // each iteration int res = 0; // Traverse the array for ( int i = 2; i < N; ++i) { // Check if L[i] forms GP if (L[i - 1] * L[i - 1] == L[i] * L[i - 2]) { ++count; } // Otherwise, update // count to 0 else { count = 0; } // Update the // final count res += count; } // Return the final // count return res; } // Driver Code public static void Main(String[] args) { // Given array arr[] int [] arr = {1, 2, 4, 8, 16, 24}; int N = arr.Length; // Function Call Console.Write(numberOfGP(arr, N)); } } // This code is contributed by Chitranayal |
Javascript
<script> // Javascript program for the above approach // Function to count all the subarrays // of size at least 3 forming GP function numberOfGP(L, N) { // If array size is less than 3 if (N <= 2) return 0; // Stores the count of subarray let count = 0; // Stores the count of subarray // for each iteration let res = 0; // Traverse the array for (let i = 2; i < N; ++i) { // Check if L[i] forms GP if (L[i - 1] * L[i - 1] == L[i] * L[i - 2]) { ++count; } // Otherwise, update count to 0 else { count = 0; } // Update the final count res += count; } // Return the final count return res; } // Driver Code // Given array arr[] let arr = [ 1, 2, 4, 8, 16, 24]; let N = arr.length; // Function Call document.write(numberOfGP(arr, N)); // This code is contributed by Mayank Tyagi </script> |
6
Time Complexity: O(N)
Auxiliary Space: O(1) as it is using constant variables