C++에서 이진 리프팅을 사용하는 N 숫자의 접두사 합에서 X보다 크거나 같은 첫 번째 요소

이 문제에서는 N개의 숫자와 정수 값 x로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 Binary Lifting을 사용하여 N개의 접두사 합에서 X보다 크거나 같은 첫 번째 요소를 찾는 프로그램을 만드는 것입니다. .

접두사 합계 배열 요소의 각 요소가 초기 배열의 해당 인덱스까지의 모든 요소의 합인 배열입니다.

예 - 배열[] ={5, 2, 9, 4, 1}

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

문제를 이해하기 위해 예를 들어 보겠습니다.

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

솔루션 접근 방식

여기에서는 바이너리 리프팅 개념을 사용하여 문제를 해결할 것입니다. . Binary Lifting은 주어진 숫자의 값을 0에서 N 사이의 2승(비트를 뒤집음으로써 수행)으로 증가시키는 것입니다.

우리는 'P' 인덱스의 초기 값을 찾을 이진 트리를 들어올리는 것과 유사한 개념을 고려할 것입니다. 이것은 값이 X보다 크지 않도록 비트를 뒤집어서 증가합니다. 이제 이 위치 'P'와 함께 리프트를 고려할 것입니다.

이를 위해 i 번째 비트 플립이 합이 X보다 커지지 않도록 숫자의 비트를 뒤집기 시작할 것입니다. 이제 'P' -

타겟 위치는 'position + 2^i 사이에 있습니다. ' 및 '위치 + 2^(i+1) ' 여기서 i번째 리프트는 값을 증가시켰습니다. 또는 대상 위치가 '위치 사이에 있습니다. ' 및 '위치 + 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