Count of pairs of Array elements which are divisible by K when concatenated | Python3 program to count pairs of array elements which are divisible by K when concatenated ; Function to calculate and return the count of pairs ; Compute power of 10 modulo k ; Calculate length of a [ i ] ; Increase count of remainder ; Calculate ( a [ i ] * 10 ^ lenj ) % k ; Calculate ( k - ( a [ i ] * 10 ^ lenj ) % k ) % k ; Increase answer by count ; If a pair ( a [ i ] , a [ i ] ) is counted ; Return the count of pairs ; Driver Code
rem = [ [ 0 for x in range ( 11 ) ] for y in range ( 11 ) ] NEW_LINE def countPairs ( a , n , k ) : NEW_LINE INDENT l = [ 0 ] * n NEW_LINE p = [ 0 ] * ( 11 ) NEW_LINE p [ 0 ] = 1 NEW_LINE for i in range ( 1 , 11 ) : NEW_LINE INDENT p [ i ] = ( p [ i - 1 ] * 10 ) % k NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT x = a [ i ] NEW_LINE while ( x > 0 ) : NEW_LINE INDENT l [ i ] += 1 NEW_LINE x //= 10 NEW_LINE DEDENT rem [ l [ i ] ] [ a [ i ] % k ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( 1 , 11 ) : NEW_LINE INDENT r = ( a [ i ] * p [ j ] ) % k NEW_LINE xr = ( k - r ) % k NEW_LINE ans += rem [ j ] [ xr ] NEW_LINE if ( l [ i ] == j and ( r + a [ i ] % k ) % k == 0 ) : NEW_LINE INDENT ans -= 1 NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT a = [ 4 , 5 , 2 ] NEW_LINE n = len ( a ) NEW_LINE k = 2 NEW_LINE print ( countPairs ( a , n , k ) ) NEW_LINE