ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยตัวเลข N และค่าจำนวนเต็ม x งานของเราคือ สร้างโปรแกรมเพื่อค้นหาองค์ประกอบแรกที่มากกว่าหรือเท่ากับ X ในผลรวมนำหน้าของตัวเลข N โดยใช้ Binary Lifting .
ผลรวมคำนำหน้า ขององค์ประกอบของอาร์เรย์คืออาร์เรย์ที่แต่ละองค์ประกอบเป็นผลรวมขององค์ประกอบทั้งหมดจนถึงดัชนีนั้นในอาร์เรย์เริ่มต้น
ตัวอย่าง − array[] ={5, 2, 9, 4, 1}
คำนำหน้าSumArray[] ={5, 7, 16, 20, 21}
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3 แนวทางการแก้ปัญหา
ในที่นี้ เราจะมาแก้ปัญหาโดยใช้แนวคิด การยกแบบไบนารี . Binary Lifting เป็นการเพิ่มค่าของตัวเลขที่กำหนดโดยยกกำลัง 2 (ทำได้โดยการพลิกบิต) ตั้งแต่ 0 ถึง N
เราจะพิจารณาแนวคิดที่คล้ายกับการยกไบนารีทรี ซึ่งเราจะพบค่าเริ่มต้นของดัชนี 'P' สิ่งนี้เพิ่มขึ้นโดยการพลิกบิตเพื่อให้แน่ใจว่าค่าไม่มากกว่า X ตอนนี้เราจะพิจารณาการเพิ่มขึ้นพร้อมกับตำแหน่ง 'P' นี้
สำหรับสิ่งนี้ เราจะเริ่มการพลิกบิตของตัวเลข โดยที่การพลิกบิตที่ i จะไม่ทำให้ผลรวมมากกว่า X ตอนนี้ เรามีสองกรณีตามค่าของ 'P' −
ตำแหน่งเป้าหมายอยู่ระหว่าง 'ตำแหน่ง + 2^i ' และ 'ตำแหน่ง + 2^(i+1) ' โดยที่การยก ith เพิ่มมูลค่า หรือตำแหน่งเป้าหมายอยู่ระหว่าง 'ตำแหน่ง ' และ 'ตำแหน่ง + 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
