Number of GP ( Geometric Progression ) subsequences of size 3 | Python3 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
from collections import defaultdict NEW_LINE def binomialCoeff ( n , k ) : NEW_LINE INDENT C = [ 0 ] * ( k + 1 ) NEW_LINE C [ 0 ] = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( min ( i , k ) , - 1 , - 1 ) : NEW_LINE C [ j ] = C [ j ] + C [ j - 1 ] NEW_LINE DEDENT return C [ k ] NEW_LINE DEDENT def subsequences ( a , n , r ) : NEW_LINE INDENT left = defaultdict ( int ) NEW_LINE right = defaultdict ( int ) NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT right [ a [ i ] ] += 1 NEW_LINE DEDENT if ( r == 1 ) : NEW_LINE INDENT for i in right : NEW_LINE INDENT ans += binomialCoeff ( right [ i ] , 3 ) NEW_LINE DEDENT return ans NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT c1 = 0 NEW_LINE c2 = 0 ; NEW_LINE if ( a [ i ] % r == 0 ) : NEW_LINE INDENT c1 = left [ a [ i ] // r ] NEW_LINE DEDENT right [ a [ i ] ] -= 1 NEW_LINE c2 = right [ a [ i ] * r ] NEW_LINE ans += c1 * c2 NEW_LINE left [ a [ i ] ] += 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 2 , 6 , 2 , 3 , 6 , 9 , 18 , 3 , 9 ] NEW_LINE n = len ( a ) NEW_LINE r = 3 NEW_LINE print ( subsequences ( a , n , r ) ) NEW_LINE DEDENT