Queries for decimal values of subarrays of a binary array | implementation of finding number represented by binary subarray ; Fills pre [ ] ; returns the number represented by a binary subarray l to r ; if r is equal to n - 1 r + 1 does not exist ; Driver Code
from math import pow NEW_LINE def precompute ( arr , n , pre ) : NEW_LINE INDENT pre [ n - 1 ] = arr [ n - 1 ] * pow ( 2 , 0 ) NEW_LINE i = n - 2 NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT pre [ i ] = ( pre [ i + 1 ] + arr [ i ] * ( 1 << ( n - 1 - i ) ) ) NEW_LINE i -= 1 NEW_LINE DEDENT DEDENT def decimalOfSubarr ( arr , l , r , n , pre ) : NEW_LINE INDENT if ( r != n - 1 ) : NEW_LINE INDENT return ( ( pre [ l ] - pre [ r + 1 ] ) / ( 1 << ( n - 1 - r ) ) ) NEW_LINE DEDENT return pre [ l ] / ( 1 << ( n - 1 - r ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 0 , 1 , 0 , 1 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE pre = [ 0 for i in range ( n ) ] NEW_LINE precompute ( arr , n , pre ) NEW_LINE print ( int ( decimalOfSubarr ( arr , 2 , 4 , n , pre ) ) ) NEW_LINE print ( int ( decimalOfSubarr ( arr , 4 , 5 , n , pre ) ) ) NEW_LINE DEDENT