First element greater than or equal to X in prefix sum of N numbers using Binary Lifting | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void MakePreSum ( int arr [ ] , int presum [ ] , int n ) { presum [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) presum [ i ] = presum [ i - 1 ] + arr [ i ] ; } int BinaryLifting ( int presum [ ] , int n , int x ) { int pos = 0 ; int LOGN = log2 ( n ) ; if ( x <= presum [ 0 ] ) return 0 ; for ( int i = LOGN ; i >= 0 ; i -- ) { if ( pos + ( 1 << i ) < n && presum [ pos + ( 1 << i ) ] < x ) { pos += ( 1 << i ) ; } } return pos + 1 ; } int main ( ) { int arr [ ] = { 2 , 5 , 7 , 1 , 6 , 9 , 12 , 4 , 6 } ; int x = 8 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int presum [ n ] = { 0 } ; MakePreSum ( arr , presum , n ) ; cout << BinaryLifting ( presum , n , x ) ; return 0 ; }