Number of GP ( Geometric Progression ) subsequences of size 3 | Java program to count GP subsequences of size 3. ; To calculate nCr DP approach ; nC0 is 1 ; Compute next row of pascal triangle using the previous row ; Returns count of G . P . subsequences 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 ; IF RATIO IS ONE ; Traverse the count in hash ; Calculating nC3 , where ' n ' is the number of times each number is repeated in the input ; 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 . * ; class GFG { static int binomialCoeff ( int n , int k ) { int [ ] C = new int [ k + 1 ] ; C [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = Math . min ( i , k ) ; j > 0 ; j -- ) C [ j ] = C [ j ] + C [ j - 1 ] ; } return C [ k ] ; } static long subsequences ( int a [ ] , int n , int r ) { HashMap < Integer , Integer > left = new HashMap < > ( ) ; HashMap < Integer , Integer > right = new HashMap < > ( ) ; long ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( right . containsKey ( a [ i ] ) ) { right . put ( a [ i ] , right . get ( a [ i ] ) + 1 ) ; } else { right . put ( a [ i ] , 1 ) ; } if ( r == 1 ) { for ( Map . Entry < Integer , Integer > i : right . entrySet ( ) ) { ans += binomialCoeff ( i . getValue ( ) , 3 ) ; } return ans ; } for ( int i = 0 ; i < n ; i ++ ) { long c1 = 0 , c2 = 0 ; if ( a [ i ] % r == 0 ) if ( left . containsKey ( a [ i ] / r ) ) c1 = left . get ( a [ i ] / r ) ; if ( right . containsKey ( a [ i ] ) ) { right . put ( a [ i ] , right . get ( a [ i ] ) - 1 ) ; } else { right . put ( a [ i ] , - 1 ) ; } if ( right . containsKey ( a [ i ] * r ) ) c2 = right . get ( a [ i ] * r ) ; ans += c1 * c2 ; if ( left . containsKey ( a [ i ] ) ) { left . put ( a [ i ] , left . get ( a [ i ] ) + 1 ) ; } else { left . put ( a [ i ] , 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 . print ( subsequences ( a , n , r ) ) ; } }