使用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中文網其他相關文章！