Phần tử đầu tiên lớn hơn hoặc bằng X trong tổng tiền tố của N số bằng cách sử dụng Binary Lifting trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N số và một giá trị nguyên x. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm phần tử đầu tiên lớn hơn hoặc bằng X trong tổng tiền tố của N số bằng cách sử dụng Binary Lifting .

Tổng tiền tố phần tử của một mảng là một mảng mà mỗi phần tử là tổng của tất cả các phần tử cho đến chỉ mục đó trong mảng ban đầu.

Ví dụ - mảng [] ={5, 2, 9, 4, 1}

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

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Ở đây, chúng ta sẽ giải quyết vấn đề bằng cách sử dụng khái niệm nâng nhị phân . Binary Lifting đang tăng giá trị của một số đã cho theo lũy thừa của 2 (được thực hiện bằng cách lật các bit) trong khoảng từ 0 đến N.

Chúng tôi sẽ xem xét một khái niệm tương tự như nâng cây nhị phân, nơi chúng tôi sẽ tìm giá trị ban đầu của chỉ số 'P'. Điều này được tăng lên bằng cách lật các bit để đảm bảo giá trị không lớn hơn X. Bây giờ, chúng tôi sẽ xem xét mức tăng cùng với vị trí 'P' này.

Đối với điều này, chúng ta sẽ bắt đầu lật các bit của số sao cho việc lật bit thứ i không làm cho tổng lớn hơn X. Bây giờ, chúng ta có hai trường hợp dựa trên giá trị của 'P' -

Vị trí mục tiêu nằm giữa ' position + 2 ^ i 'và' vị trí + 2 ^ (i + 1) 'trong đó lần nâng thứ i đã tăng giá trị. Hoặc, vị trí mục tiêu nằm giữa ' vị trí 'và' vị trí + 2 ^ i '.

Sử dụng điều này, chúng tôi sẽ xem xét vị trí chỉ mục.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tô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;
}

Đầu ra

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