Subsequences of size three in an array whose sum is divisible by m | Python program to find count of subsequences of size three divisible by M . ; Storing frequencies of all remainders when divided by M . ; including i and j in the sum rem calculate the remainder required to make the sum divisible by M ; if the required number is less than j , we skip as we have already calculated for that value before . As j here starts with i and rem is less than j . ; if satisfies the first case . ; if satisfies the second case ; if satisfies the third case ; Driver code
def countSubSeq ( A , N , M ) : NEW_LINE INDENT ans = 0 NEW_LINE h = [ 0 ] * M NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT A [ i ] = A [ i ] % M NEW_LINE h [ A [ i ] ] = h [ A [ i ] ] + 1 NEW_LINE DEDENT for i in range ( 0 , M ) : NEW_LINE INDENT for j in range ( i , M ) : NEW_LINE INDENT rem = ( M - ( i + j ) % M ) % M NEW_LINE if ( rem < j ) : NEW_LINE INDENT continue NEW_LINE DEDENT if ( i == j and rem == j ) : NEW_LINE INDENT ans = ans + h [ i ] * ( h [ i ] - 1 ) * ( h [ i ] - 2 ) / 6 NEW_LINE DEDENT elif ( i == j ) : NEW_LINE INDENT ans = ans + ( h [ i ] * ( h [ i ] - 1 ) * h [ rem ] / 2 ) NEW_LINE DEDENT elif ( i == rem ) : NEW_LINE INDENT ans = ans + h [ i ] * ( h [ i ] - 1 ) * h [ j ] / 2 NEW_LINE DEDENT elif ( rem == j ) : NEW_LINE INDENT ans = ans + h [ j ] * ( h [ j ] - 1 ) * h [ i ] / 2 NEW_LINE DEDENT else : NEW_LINE INDENT ans = ans + h [ i ] * h [ j ] * h [ rem ] NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT DEDENT M = 3 ; NEW_LINE A = [ 1 , 2 , 4 , 3 ] NEW_LINE N = len ( A ) NEW_LINE print ( countSubSeq ( A , N , M ) ) NEW_LINE