หาตัวอักษร Index i ของ Binary String หลัง n รอบการแปลง (0→01, 1→10) ใน C++

Binary String เริ่มต้น ทำ n รอบ: 0→01, 1→10 หาตัวอักษร Index i หลังรอบที่ n

ตัวอย่าง: "101", n=2, i=3

• Round 1: 1→10, 0→01, 1→10 = "100110"
• Round 2: "100101101001" → Index 3 = '1'

อัลกอริทึม (Simulation)

จำลองการแปลง n รอบ แล้วคืนค่า Index i

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

char getCharacter(string bin_str, int n, int i) {
    string temp = "";
    for (int round = 0; round < n; round++) {
        for (char c : bin_str) {
            if (c == '1') temp += "10";
            else temp += "01";
        }
        bin_str = temp;
        temp = "";
    }
    return bin_str[i];
}

int main() {
    int n = 2;
    string bin = "101";
    cout << "3rd character is: " << getCharacter(bin, n, 3) << endl;
    cout << "9th character is: " << getCharacter(bin, n, 9);
    return 0;
}

ผลลัพธ์

3rd character is: 1
9th character is: 0

Optimization: O(log k) โดยไม่สร้าง String

สังเกต: ความยาว Double ทุก รอบ (Len × 2^n)

สามารถหาตัวอักษร Index k ได้โดย Recursive:

char kthChar(string& s, int n, long long k) {
    if (n == 0) return s[k];
    long long half = s.length() * (1LL << (n-1));
    if (k < half) return kthChar(s, n-1, k);
    else return (kthChar(s, n-1, k - half) == '0') ? '1' : '0';
}

แต่ต้องคำนวณความยาวเริ่มต้น × 2^n ซึ่งอาจ Overflow

ข้อจำกัด

Simulation ใช้ได้ก็ต่อเมื่อ n และความยาว String ไม่ใหญ่เกินไป (ความยาวสุดท้าย = Len × 2^n)