Count all prefixes of the given binary array which are divisible by x | Function to return the count of total binary prefix which are divisible by x ; Initialize with zero ; Instead of converting all prefixes to decimal , take reminder with x ; If number is divisible by x then reminder = 0 ; Driver code
def CntDivbyX ( arr , n , x ) : NEW_LINE INDENT number = 0 NEW_LINE count = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT number = ( number * 2 + arr [ i ] ) % x NEW_LINE if number == 0 : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT arr = [ 1 , 0 , 1 , 0 , 1 , 1 , 0 ] NEW_LINE n = 7 NEW_LINE x = 2 NEW_LINE print ( CntDivbyX ( arr , n , x ) ) NEW_LINE