Given an array of N integers and a number X. The task is to find the index of first element which is greater than or equal to X in prefix sums of N numbers.
Examples:
Input: arr[] = { 2, 5, 7, 1, 6, 9, 12, 4, 6 } and x = 8
Output: 2
prefix sum array formed is { 2, 7, 14, 15, 21, 30, 42, 46, 52}, hence 14 is the number whose index is 2Input: arr[] = { 2, 5, 7, 1, 6, 9, 12, 4, 6 } and x = 30
Output: 5
Approach: The problem can be solved using lower_bound function in Binary search. But in this post, the problem will be solved using Binary-Lifting. In binary lifting, a value is increased (or lifted) by powers of 2, starting with the highest possible power of 2(log(N)) down to the lowest power(0).
- Initialize position = 0 and set each bit of position, from most significant bit to least significant bit.
- Whenever a bit is set to 1, the value of position increases (or lifts).
- While increasing or lifting position, make sure that prefix sum till position should be less than v.
- Here, log(N) bits are needed for all possible values of ‘position’ ( from log(N)th to 0th bit ).
- Determine the value of the i-th bit. First, check if setting the i-th bit won’t make ‘position’ greater than N, which is the size of the array. Before lifting to the new ‘position’, check that value at that new ‘position’ is less than X or not.
- If this condition is true, then target position lies above the ‘position’ + 2^i, but below the ‘position’ + 2^(i+1). This is because if the target position was above ‘position’ + 2^(i+1), then the position would have been already lifted by 2^(i+1) (this logic is similar to binary lifting in trees).
- If it is false, then the target value lies between ‘position’ and ‘position’ + 2^i, so try to lift by a lower power of 2. Finally, the loop will end such that the value at that position is less than X. Here, in this question, the lower bound is asked. So, return ‘position’ + 1.
Below is the implementation of the above approach:
C++
// CPP program to find lower_bound of x in// prefix sums array using binary lifting.#include <bits/stdc++.h>using namespace std;// function to make prefix sums arrayvoid 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];}// function to find lower_bound of x in// prefix sums array using binary lifting.int BinaryLifting(int presum[], int n, int x){ // initialize position int pos = 0; // find log to the base 2 value of n. int LOGN = log2(n); // if x less than first number. if (x <= presum[0]) return 0; // starting from most significant bit. for (int i = LOGN; i >= 0; i--) { // if value at this position less // than x then updateposition // Here (1<<i) is similar to 2^i. if (pos + (1 << i) < n && presum[pos + (1 << i)] < x) { pos += (1 << i); } } // +1 because 'pos' will have position // of largest value less than 'x' return pos + 1;}// Driver codeint main(){ // given array int arr[] = { 2, 5, 7, 1, 6, 9, 12, 4, 6 }; // value to find int x = 8; // size of array int n = sizeof(arr) / sizeof(arr[0]); // to store prefix sum int presum[n] = { 0 }; // call for prefix sum MakePreSum(arr, presum, n); // function call cout << BinaryLifting(presum, n, x); return 0;} |
Java
// Java program to find lower_bound of x in// prefix sums array using binary lifting.import java.util.*;class solution{// function to make prefix sums arraystatic 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];}// function to find lower_bound of x in// prefix sums array using binary lifting.static int BinaryLifting(int []presum, int n, int x){ // initialize position int pos = 0; // find log to the base 2 value of n. int LOGN = (int)Math.log(n); // if x less than first number. if (x <= presum[0]) return 0; // starting from most significant bit. for (int i = LOGN; i >= 0; i--) { // if value at this position less // than x then updateposition // Here (1<<i) is similar to 2^i. if (pos + (1 << i) < n && presum[pos + (1 << i)] < x) { pos += (1 << i); } } // +1 because 'pos' will have position // of largest value less than 'x' return pos + 1;}// Driver codepublic static void main(String args[]){ // given array int []arr = { 2, 5, 7, 1, 6, 9, 12, 4, 6 }; // value to find int x = 8; // size of array int n = arr.length; // to store prefix sum int []presum = new int[n]; Arrays.fill(presum,0); // call for prefix sum MakePreSum(arr, presum, n); // function call System.out.println(BinaryLifting(presum, n, x));}} |
Python 3
# Python 3 program to find # lower_bound of x in prefix # sums array using binary lifting.import math# function to make prefix # sums arraydef MakePreSum( arr, presum, n): presum[0] = arr[0] for i in range(1, n): presum[i] = presum[i - 1] + arr[i]# function to find lower_bound of x in# prefix sums array using binary lifting.def BinaryLifting(presum, n, x): # initialize position pos = 0 # find log to the base 2 # value of n. LOGN = int(math.log2(n)) # if x less than first number. if (x <= presum[0]): return 0 # starting from most significant bit. for i in range(LOGN, -1, -1) : # if value at this position less # than x then updateposition # Here (1<<i) is similar to 2^i. if (pos + (1 << i) < n and presum[pos + (1 << i)] < x) : pos += (1 << i) # +1 because 'pos' will have position # of largest value less than 'x' return pos + 1# Driver codeif __name__ == "__main__": # given array arr = [ 2, 5, 7, 1, 6, 9, 12, 4, 6 ] # value to find x = 8 # size of array n = len(arr) # to store prefix sum presum = [0] * n # call for prefix sum MakePreSum(arr, presum, n) # function call print(BinaryLifting(presum, n, x))# This code is contributed# by ChitraNayal |
C#
// C# program to find lower_bound of x in// prefix sums array using binary lifting.using System;class GFG{ // function to make prefix sums array static 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]; } // function to find lower_bound of x in // prefix sums array using binary lifting. static int BinaryLifting(int []presum, int n, int x) { // initialize position int pos = 0; // find log to the base 2 value of n. int LOGN = (int)Math.Log(n); // if x less than first number. if (x <= presum[0]) return 0; // starting from most significant bit. for (int i = LOGN; i >= 0; i--) { // if value at this position less // than x then updateposition // Here (1<<i) is similar to 2^i. if (pos + (1 << i) < n && presum[pos + (1 << i)] < x) { pos += (1 << i); } } // +1 because 'pos' will have position // of largest value less than 'x' return pos + 1; } // Driver code public static void Main() { // given array int []arr = { 2, 5, 7, 1, 6, 9, 12, 4, 6 }; // value to find int x = 8; // size of array int n = arr.Length; // to store prefix sum int []presum = new int[n]; // call for prefix sum MakePreSum(arr, presum, n); // function call Console.WriteLine(BinaryLifting(presum, n, x)); }}// This code has been contributed// by PrinciRaj1992 |
Javascript
<script>// Javascript program to find lower_bound of x in// prefix sums array using binary lifting. // function to make prefix sums array function MakePreSum(arr,presum,n) { presum[0] = arr[0]; for (let i = 1; i < n; i++) presum[i] = presum[i - 1] + arr[i]; } // function to find lower_bound of x in// prefix sums array using binary lifting.function BinaryLifting(presum, n,k){ // initialize position let pos = 0; // find log to the base 2 value of n. let LOGN = Math.log(n); // if x less than first number. if (x <= presum[0]) return 0; // starting from most significant bit. for (let i = LOGN; i >= 0; i--) { // if value at this position less // than x then updateposition // Here (1<<i) is similar to 2^i. if (pos + (1 << i) < n && presum[pos + (1 << i)] < x) { pos += (1 << i); } } // +1 because 'pos' will have position // of largest value less than 'x' return pos + 1;}// Driver code// given arraylet arr=[2, 5, 7, 1, 6, 9, 12, 4, 6];// value to findlet x = 8;// size of arraylet n = arr.length;// to store prefix sumlet presum = new Array(n);for(let i=0;i<n;i++){ presum[i]=0;}// call for prefix sumMakePreSum(arr, presum, n);// function calldocument.write(BinaryLifting(presum, n, x)); // This code is contributed by avanitrachhadiya2155</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
