First element greater than or equal to X in prefix sum of N numbers using Binary Lifting | Python 3 program to find lower_bound of x in prefix sums array using binary lifting . ; function to make prefix sums array ; function to find lower_bound of x in prefix sums array using binary lifting . ; initialize position ; find log to the base 2 value of n . ; if x less than first number . ; starting from most significant bit . ; if value at this position less than x then updateposition Here ( 1 << i ) is similar to 2 ^ i . ; + 1 because ' pos ' will have position of largest value less than 'x ; Driver code ; given array ; value to find ; size of array ; to store prefix sum ; call for prefix sum ; function call
import math NEW_LINE def MakePreSum ( arr , presum , n ) : NEW_LINE INDENT presum [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT presum [ i ] = presum [ i - 1 ] + arr [ i ] NEW_LINE DEDENT DEDENT def BinaryLifting ( presum , n , x ) : NEW_LINE INDENT pos = 0 NEW_LINE LOGN = int ( math . log2 ( n ) ) NEW_LINE if ( x <= presum [ 0 ] ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT for i in range ( LOGN , - 1 , - 1 ) : NEW_LINE INDENT if ( pos + ( 1 << i ) < n and presum [ pos + ( 1 << i ) ] < x ) : NEW_LINE INDENT pos += ( 1 << i ) NEW_LINE DEDENT DEDENT DEDENT ' NEW_LINE INDENT return pos + 1 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 5 , 7 , 1 , 6 , 9 , 12 , 4 , 6 ] NEW_LINE x = 8 NEW_LINE n = len ( arr ) NEW_LINE presum = [ 0 ] * n NEW_LINE MakePreSum ( arr , presum , n ) NEW_LINE print ( BinaryLifting ( presum , n , x ) ) NEW_LINE DEDENT