Tìm N số khác nhau có OR bitwise bằng K trong C++

Khái niệm

Cho hai số nguyên N và K. Tìm N số nguyên khác nhau có OR bitwise bằng K. Nếu không tồn tại, in -1.

Ví dụ 1

Đầu vào: N = 4, K = 6

Đầu ra: 6 0 1 2

Ví dụ 2

Đầu vào: N = 11, K = 6

Đầu ra: -1 (không thể)

Phương pháp

• Nếu OR bitwise của dãy là K thì mọi vị trí bit 0 trong K phải là 0 trong tất cả số.
• Chỉ có thể thay đổi ở các vị trí bit 1 trong K. Gọi số bit 1 là Bit_K.
• Có thể tạo 2^Bit_K số khác nhau với Bit_K bit. Nếu lấy K làm một số, còn N-1 số tạo từ các hoán vị bit khác K.
• Nếu 2^Bit_K < N thì không thể.

Ví dụ

#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 ans1 = 1;
    for (int i = 0; i < MAX1; i++) {
        pow2[i] = ans1;
        ans1 *= 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);
    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;
}

Đầu ra

6 0 1 2