หาสตริงไบนารีลำดับที่ N ในลำดับเรียงเลขologico ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวก N งานของเราคือการหาสตริงไบนารีลำดับที่ N ในลำดับเรียงลำดับพจนานุกรม (lexicographical order)

เราต้องหาสตริงตัวที่ N ในรายการอนันต์ที่สร้างจากสัญลักษณ์ 2 ตัวคือ a และ b เรียงตามลำดับพจนานุกรม

รายการคือ −

a, b, aa, ab, ba, bb, aaa, aab, aba, …

ตัวอย่างเพื่อความเข้าใจ

Input : N = 8 
Output : aab

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

วิธีง่ายคือใช้ลูปสร้างสตริงทั้ง N ตัว แล้วคืนค่าตัวที่ N แต่วิธีนี้ไม่มีประสิทธิภาพสำหรับ N ใหญ่

วิธีที่ดีกว่า: ใช้ Relative Index โดยใช้ข้อเท็จจริงว่าจำนวนสตริงความยาว N ที่สร้างจาก 2 สัญลักษณ์ได้คือ 2^N เราสามารถใช้ relative index เพื่อหา รูปแบบไบนารี ของสตริง

Relative index = N + 1 - 2^floor(log₂(N+1))

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

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

#define ll long long int

string findBinString(ll n) {
    ll len = (int)log2(n + 1);
    int ri = n + 1 - pow(2, len);
    ll i = 0;
    string binString = "";
    
    for (i = 0; i < len; i++) {
        binString += 'a';
    }
    
    i = 0;
    while (ri > 0) {
        if (ri % 2 == 1)
            binString[i] = 'b';
        ri /= 2;
        i++;
    }
    
    reverse(binString.begin(), binString.end());
    return binString;
}

int main() {
    ll n = 245;
    cout << "The " << n << "-th binary string in sorted order is " << findBinString(n);
    return 0;
}

ผลลัพธ์

The 245-th binary string in sorted order is bbbabba