Number of GP ( Geometric Progression ) subsequences of size 3 | Python3 program to count GP subsequences of size 3. ; 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 ; 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 subsequences ( a , n , r ) : NEW_LINE INDENT left = defaultdict ( lambda : 0 ) NEW_LINE right = defaultdict ( lambda : 0 ) NEW_LINE ans = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT c1 , c2 = 0 , 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