使用C++中的二进制提升，在N个数字的前缀和中找到第一个大于或等于X的元素

在这个问题中，我们得到一个由 N 个数字和一个整数值 x 组成的数组 arr[]。我们的任务是创建一个程序，使用二进制提升在 N 个数字的前缀和中查找大于或等于 X 的第一个元素。

前缀和数组元素的强>是一个数组，其每个元素是初始数组中直到该索引为止的所有元素的总和。

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

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

让我们举个例子来理解这个问题，

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

解决方案

在这里，我们将使用二元提升的概念来解决问题。二元提升是将给定数字的值增加 2 的幂（通过翻转位完成），范围从 0 到 N。

我们将考虑一个类似于提升二叉树的概念，我们将在其中找到“P”指数的初始值。这是通过翻转位来增加的，确保该值不大于 X。现在，我们将考虑这个位置“P”的升力。

为此，我们将开始翻转数字的位，例如第 i 位翻转不会使总和大于 X。现在，根据 'P' 的值，我们有两种情况 -

目标位置位于 'position + 2 之间^i”和“位置 + 2^(i+1)”，其中第 i 次提升增加了值。或者，目标位置位于“position”和“position + 2^i”之间。

使用此我们将考虑索引位置。

示例

说明我们解决方案工作原理的程序

#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;
}

输出

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

以上是使用C++中的二进制提升，在N个数字的前缀和中找到第一个大于或等于X的元素的详细内容。更多信息请关注PHP中文网其他相关文章！