Modulo of a large Binary String | Function to return the value of ( str % k ) ; pwrTwo [ i ] will store ( ( 2 ^ i ) % k ) ; To store the result ; If current bit is 1 ; Add the current power of 2 ; Driver code
def getMod ( _str , n , k ) : NEW_LINE INDENT pwrTwo = [ 0 ] * n NEW_LINE pwrTwo [ 0 ] = 1 % k NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT pwrTwo [ i ] = pwrTwo [ i - 1 ] * ( 2 % k ) NEW_LINE pwrTwo [ i ] %= k NEW_LINE DEDENT res = 0 NEW_LINE i = 0 NEW_LINE j = n - 1 NEW_LINE while ( i < n ) : NEW_LINE INDENT if ( _str [ j ] == '1' ) : NEW_LINE INDENT res += ( pwrTwo [ i ] ) NEW_LINE res %= k NEW_LINE DEDENT i += 1 NEW_LINE j -= 1 NEW_LINE DEDENT return res NEW_LINE DEDENT _str = "1101" NEW_LINE n = len ( _str ) NEW_LINE k = 45 NEW_LINE print ( getMod ( _str , n , k ) ) NEW_LINE