Number of GP ( Geometric Progression ) subsequences of size 3 | Java program to count GP subsequences of size 3. ; Returns count of G . P . subsequneces with length 3 and common ratio r ; Hashing to maintain left and right array elements to the main count ; Stores the answer ; Traverse through the elements ; Keep the count in the hash ; Traverse through all elements and find out the number of elements as k1 * k2 ; Keep the count of left and right elements left is a [ i ] / r and right a [ i ] * r ; If the current element is divisible by k , count elements in left hash . ; Decrease the count in right hash ; Number of right elements ; Calculate the answer ; left count of a [ i ] ; Returns answer ; Driver Code
import java . util . * ; import java . lang . * ; class GFG { static long subsequences ( int a [ ] , int n , int r ) { Map < Integer , Integer > left = new HashMap < > ( ) , right = new HashMap < > ( ) ; long ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) right . put ( a [ i ] , right . getOrDefault ( a [ i ] , 0 ) + 1 ) ; for ( int i = 0 ; i < n ; i ++ ) { long c1 = 0 , c2 = 0 ; if ( a [ i ] % r == 0 ) c1 = left . getOrDefault ( a [ i ] / r , 0 ) ; right . put ( a [ i ] , right . getOrDefault ( a [ i ] , 0 ) - 1 ) ; c2 = right . getOrDefault ( a [ i ] * r , 0 ) ; ans += c1 * c2 ; left . put ( a [ i ] , left . getOrDefault ( a [ i ] , 0 ) + 1 ) ; } return ans ; } public static void main ( String [ ] args ) { int a [ ] = { 1 , 2 , 6 , 2 , 3 , 6 , 9 , 18 , 3 , 9 } ; int n = a . length ; int r = 3 ; System . out . println ( subsequences ( a , n , r ) ) ; } }