Find the first element greater than or equal to X in the prefix sum of N numbers using binary lifting in C++

In this problem, we are given an array arr[] consisting of N numbers and an integer value x. Our task is to create a program that uses binary promotion to find the first element in a prefix sum of N numbers that is greater than or equal to X.

prefix sum 数组元素的强> is an array whose each element is the sum of all elements in the initial array up to that index.

Example - array[] = {5, 2, 9, 4, 1}

prefixSumArray[] = {5, 7, 16, 20, 21}

Let us take an example to understand this problem,

Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3

Solution

Here we will use the concept of binary lifting to solve it question. Binary promotion increases the value of a given number by a power of 2 (done by flipping bits), ranging from 0 to N.

We will consider a concept similar to boosted binary tree, where we will find the initial value of the "P" index. This is increased by flipping bits, ensuring that the value is no greater than X. Now, we will consider the lift force at this position "P".

To do this, we will start flipping the bits of the number, for example flipping the i-th bit will not make the sum greater than X. Now, depending on the value of 'P', we have two cases -

target position is between 'position 2^i" and "position 2^(i 1) ", where the i-th lift increases the value. Alternatively, the target position is between "position" and "position 2^i".

Using this we will consider the index position.

Example

Program illustrating how our solution works

#include <iostream>
#include <math.h>
using namespace std;
void generatePrefixSum(int arr[], int prefSum[], int n){
   prefSum[0] = arr[0];
   for (int i = 1; i < n; i++)
      prefSum[i] = prefSum[i - 1] + arr[i];
}
int findPreSumIndexBL(int prefSum[], int n, int x){
   int P = 0;
   int LOGN = log2(n);
   if (x <= prefSum[0])
      return 0;
   for (int i = LOGN; i >= 0; i--) {
      if (P + (1 << i) < n &&
         prefSum[P + (1 << i)] < x) {
         P += (1 << i);
      }
   }
   return P + 1;
}
int main(){
   int arr[] = { 5, 2, 9, 4, 1 };
   int X = 19;
   int n = sizeof(arr) / sizeof(arr[0]);
   int prefSum[n] = { 0 };
   generatePrefixSum(arr, prefSum, n);
   cout<<"The index of first elements of the array greater than the given number is ";
   cout<<findPreSumIndexBL(prefSum, n, X);
   return 0;
}

Output

The index of first elements of the array greater than the given number is 3

The above is the detailed content of Find the first element greater than or equal to X in the prefix sum of N numbers using binary lifting in C++. For more information, please follow other related articles on the PHP Chinese website!