การสืบค้นค่าทศนิยมของ Subarray ของอาร์เรย์ไบนารีใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ไบนารี bin[] และ Q queries แต่ละ query ประกอบด้วย 2 ค่า L และ R ภารกิจคือสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นค่าทศนิยมของ subarray ของอาร์เรย์ไบนารีใน C++

คำอธิบายปัญหา

เพื่อแก้แต่ละ query เราต้องหาและพิมพ์เลขทศนิยมที่สร้างขึ้นจาก subarray เริ่มจาก L ถึง R คือ subarray[L...R]

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6

เอาต์พุต

2
101

คำอธิบาย

Query 1: subarray ที่ได้คือ { 0, 0, 1, 0} สร้างเลขไบนารี 0010 ซึ่งแปลงเป็นทศนิยมได้ 2

Query 2: subarray ที่ได้คือ { 1, 1, 0, 0, 1, 0, 1} สร้างเลขไบนารี 1100101 ซึ่งแปลงเป็นทศนิยมได้ 101

แนวทางแก้ปัญหา

วิธีง่าย คือการวนลูปผ่านอาร์เรย์ไบนารีจากดัชนี L ถึง R หาเลขไบนารีที่สร้างขึ้น แล้วแปลงเลขไบนารีนั้นเป็นทศนิยม

ตัวอย่างโปรแกรม (วิธีแบบง่าย)

#include <iostream>
#include <math.h>
using namespace std;

int CalcDecimalValue(int bin[], int L, int R) {
    int decimal = 0;
    int j = 0;
    for(int i = R; i >= L; i--) {
        decimal += bin[i] * pow(2, j);
        j++;
    }
    return decimal;
}

int main() {
    int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
    int n = sizeof(bin) / sizeof(bin[0]);
    int Q = 2;
    int query[Q][2] = {{2, 5}, {0, 6}};
    for(int i = 0; i < Q; i++) {
        cout << "For query " << (i+1) << ": The decimal value of subarray is " << CalcDecimalValue(bin, query[i][0], query[i][1]) << "\n";
    }
    return 0;
}

เอาต์พุต

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101

วิธีอีกวิธีหนึ่ง คือการใช้อาร์เรย์ที่คำนวณล่วงหน้า (pre-computed array) เราจะสร้างอาร์เรย์ที่เก็บเลขทศนิยมที่สร้างขึ้นจนถึงดัชนี (n-i) และสำหรับการแก้ query เราจะหาผลต่างระหว่างค่าที่ l และ r

ค่าที่ i ของอาร์เรย์จะหาได้จากสูตรการแปลงไบนารีเป็นทศนิยม เริ่มจากด้านขวา (n-1):

decimalArray[i] = bin[i]*2^(n-1-i) + bin[i+1]*2^(n-1-i+1) + ... + bin[n-1]*2^(0)

ตัวอย่างโปรแกรม (วิธี Pre-computed Array)

#include <bits/stdc++.h>
using namespace std;

int decimalArray[1000];

void createDecimalArray(int bin[], int n) {
    memset(decimalArray, 0, n*sizeof(int));
    decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2, (n - 1 - i)));
}

int CalcDecimalValue(int L, int R, int n) {
    if (R != n - 1)
        return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
    return decimalArray[L] / (1 << (n - 1 - R));
}

int main() {
    int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
    int n = sizeof(bin) / sizeof(bin[0]);
    createDecimalArray(bin, n);
    int Q = 2;
    int query[Q][2] = {{2, 5}, {0, 6}};
    for(int i = 0; i < Q; i++) {
        cout << "For query " << (i+1) << ": The decimal value of subarray is " << CalcDecimalValue(query[i][0], query[i][1], n) << "\n";
    }
    return 0;
}

เอาต์พุต

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101