Number of GP sequence Problem in Java

The number of GP sequence problems in Java involves determining the count of valid geometric progression sequences within a given set of numbers. Geometric progressions, defined by a common ratio, are essential in various fields. In this tutorial, we will find the count of GP sequence that has the length 3.

Example 1:

Input: inputArray[] = {1, 2, 6, 2, 3, 6, 9, 18, 3, 9}, commonRatio = 3

Output: The count of GP subsequences with length 3 and common ratio 3 is: 6

Explanation: The program calculates that there are 6 geometric progression (GP) subsequences of length 3 with a common ratio of 3 in the specified array.

Example 2:

Input: inputArray[] = {1, 3, 9, 27, 81}, commonRatio = 3

Output: The count of GP subsequences with length 3 and common ratio 3 is: 3

Explanation: The GP subsequences are {1, 3, 9}, {3, 9, 27}, and {9, 27, 81}.

Approach: Naive Approach

In the naive approach, the algorithm iterates through every triplet of elements in the array, checking if they form a geometric progression subsequence. The triple-nested iteration results in cubic time complexity, making it less efficient for larger input sizes due to its exhaustive nature.

Algorithm:

Step 1: Initialize Two HashMaps: Create left and right HashMaps to count the occurrences of each element to the left and right of the current element in the array.

Step 2: Populate Right HashMap: Iterate through the array and populate the right HashMap with the count of each element.

Step 3: Count GP Subsequences by Iterate through each array element.

Step 4: For the current element array[i]:

Step 4.1: Calculate countLeft using the left HashMap if array[i] is divisible by the ratio.

Step 4.2: Reduce array[i]'s count in the right HashMap.

Step 4.3: Determine countRight for array[i] * ratio in the right HashMap.

Step 4.4: Multiply countLeft and countRight to update the total subsequence count (result).

Step 4.5: Increment array[i]'s count in the left HashMap.

Step 6: Return Total Count: Return the total count of subsequences (result) after iterating through the array.

Implementation:

Filename: MyGPProgram.java

Output:

The count of GP subsequences with length 3 and common ratio 3 is: 6 

Time Complexity: The time complexity is O(n) as it utilizes two loops that iterate through the input array, and the operations inside each loop are constant time, resulting in a linear overall time complexity.

Auxiliary Space: The auxiliary space complexity is O(n) because the code employs two HashMaps to maintain counts of elements, and the space required by these HashMaps scales linearly with the size of the input array.

Approach: Counting Geometric Progression (G.P.) Subsequences

The code employs a counting approach for Geometric Progression (G.P.) subsequences, utilizing hash maps to track element occurrences and efficiently calculate the count based on the given ratio. Additionally, the code leverages binomial coefficients to compute combinations, enhancing the accuracy of G.P. subsequence counts.

Algorithm:

Step 1: Calculate the binomial coefficient (n choose k) using dynamic programming in binomialCoeff.

Step 2: In countGPSubsequences, use left and right HashMaps to track the counts of elements to the left and right of the current element.

Step 3: If the ratio is 1, calculate GP subsequences using the binomial coefficient for each element's count.

Step 4: if not, iterate through the array:

• Update leftCount based on the left HashMap if the current element is divisible by the ratio.
• Adjust rightCount based on the right HashMap for the element times the ratio.
• Update the total count of subsequences using leftCount and rightCount.
• Update counts in left and right HashMaps accordingly.

Step 5: Define the array, size, and the common ratio. Call countGPSubsequences and print the result.

Implementation:

Filename: GPSequence.java

Output:

Count of GP subsequences with commonRatio 3: 6 

Time Complexity: The outer loop in countGPSubsequences iterates through all array elements once, resulting in a time complexity of O(n), where n is the size of the input array.

Auxiliary Space: The space complexity is influenced by the two hash maps (left and right). In the worst case, where all elements are unique, the space complexity would be O(n) since each element may have an entry in both hash maps.