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