Number of GP ( Geometric Progression ) subsequences of size 3 | C ++ 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 program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int binomialCoeff ( int n , int k ) { int C [ k + 1 ] ; memset ( C , 0 , sizeof ( C ) ) ; C [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = min ( i , k ) ; j > 0 ; j -- ) C [ j ] = C [ j ] + C [ j - 1 ] ; } return C [ k ] ; } long long subsequences ( int a [ ] , int n , int r ) { unordered_map < int , int > left , right ; long long ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) right [ a [ i ] ] ++ ; if ( r == 1 ) { for ( auto i : right ) { ans += binomialCoeff ( i . second , 3 ) ; } return ans ; } for ( int i = 0 ; i < n ; i ++ ) { long long c1 = 0 , c2 = 0 ; if ( a [ i ] % r == 0 ) c1 = left [ a [ i ] / r ] ; right [ a [ i ] ] -- ; c2 = right [ a [ i ] * r ] ; ans += c1 * c2 ; left [ a [ i ] ] ++ ; } return ans ; } int main ( ) { int a [ ] = { 1 , 2 , 6 , 2 , 3 , 6 , 9 , 18 , 3 , 9 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int r = 3 ; cout << subsequences ( a , n , r ) ; return 0 ; }