หา N จำนวนที่ต่างกันซึ่ง Bitwise OR เท่ากับ K ใน C++

แนวคิด

กำหนดจำนวนเต็ม N และ K หา N จำนวนเต็มที่ต่างกันซึ่ง Bitwise OR ของทั้งหมดเท่ากับ K หาไม่ได้ให้พิมพ์ -1

ตัวอย่างที่ 1

Input: N = 4, K = 6
Output: 6 0 1 2

ตัวอย่างที่ 2

Input: N = 11, K = 6
Output: -1 (ไม่สามารถหาได้)

หลักการ

• ถ้า Bitwise OR ของลำดับเท่ากับ K → บิตที่เป็น 0 ใน K ต้องเป็น 0 ในทุกจำนวน
• มีเพียงตำแหน่งบิตที่เป็น 1 ใน K เท่านั้นที่สามารถเปลี่ยนแปลงได้ ให้จำนวนบิตนี้ = Bit_K
• สามารถสร้างจำนวนที่ต่างกันได้สูงสุด 2^Bit_K จำนวน (รวม K เอง)
• ถ้า 2^Bit_K < N → หาคำตอบไม่ได้

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

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

#define ll long long int
#define MAX1 32
ll pow2[MAX1];
bool visited1[MAX1];
vector<int> ans1;

void power_2() {
    ll ans = 1;
    for (int i = 0; i < MAX1; i++) {
        pow2[i] = ans;
        ans *= 2;
    }
}

int countSetBits(ll x1) {
    int setBits1 = 0;
    while (x1 != 0) {
        x1 = x1 & (x1 - 1);
        setBits1++;
    }
    return setBits1;
}

void add(ll num1) {
    int point1 = 0;
    ll value1 = 0;
    for (ll i = 0; i < MAX1; i++) {
        if (visited1[i]) continue;
        else {
            if (num1 & 1)
                value1 += (1 << i);
            num1 /= 2;
        }
    }
    ans1.push_back(value1);
}

void solve(ll n1, ll k1) {
    ans1.push_back(k1);  // ใช้ K เองเป็นตัวหนึ่ง
    int countk1 = countSetBits(k1);
    
    if (pow2[countk1] < n1) {
        cout << -1;
        return;
    }
    
    int count1 = 0;
    for (ll i = 0; i < pow2[countk1] - 1; i++) {
        add(i);
        count1++;
        if (count1 == n1) break;
    }
    
    for (int i = 0; i < n1; i++)
        cout << ans1[i] << " ";
}

int main() {
    ll n1 = 4, k1 = 6;
    power_2();
    solve(n1, k1);
    return 0;
}

ผลลัพธ์

6 0 1 2