Bitwise OR ของ N สตริงไบนารีใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ bin[] ขนาด n ของสตริงไบนารี ภารกิจคือการสร้างโปรแกรมเพื่อหา Bitwise OR (|) ของ n สตริงไบนารี

ที่นี่ เราจะนำตัวเลขทั้งหมดมาหา bitwise OR ของพวกมัน คือ bin[0] | bin[1] | ... bin[n-2] | bin[n]

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

อินพุต −

bin[] = {"1001", "11001", "010101"}

เอาต์พุต −

011101

คำอธิบาย − Bitwise OR ของสตริงไบนารีทั้งหมด −

(1001) | (11001) | (010101) = 011101

เพื่อแก้ปัญหานี้ เราจะหาสตริงที่มีจำนวนบิตมากที่สุด (สตริงที่ยาวที่สุด) จากนั้นเพิ่ม 0 นำหน้า (leading zeros) ให้กับสตริงอื่นๆ ให้ครบ แล้วค่อยหา Bitwise OR ของบิตแต่ละตำแหน่ง

ตัวอย่างการทำงานของอัลกอริทึม

bin[] = {"1101", "011010", "00111"}

สตริงที่ยาวที่สุดคือ "011010" ความยาว 6 ดังนั้นเราจะเพิ่ม 0 นำหน้าสตริงอื่นๆ

สตริงที่อัปเดตแล้ว − "001101", "011010", "000111"

หา BITWISE OR ของทุกสตริง − 001101 | 011010 | 000111 = 011111

ตัวอย่างโปรแกรม

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

string bitwiseOR(string* bin, int n) {
    string result;
    int max_size = INT_MIN;
    for (int i = 0; i < n; i++) {
        max_size = max(max_size, (int)bin[i].size());
        reverse(bin[i].begin(), bin[i].end());
    }
    for (int i = 0; i < n; i++) {
        string s;
        for (int j = 0; j < max_size - bin[i].size(); j++) s += '0';
        bin[i] = bin[i] + s;
    }
    for (int i = 0; i < max_size; i++) {
        int insertBit = 0;
        for (int j = 0; j < n; j++)
            insertBit = insertBit | (bin[j][i] - '0');
        result += (insertBit + '0');
    }
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string bin[] = { "1101", "011010", "00111" };
    int n = sizeof(bin) / sizeof(bin[0]);
    cout << "The bitwise OR of all the binary String of the string array is " << bitwiseOR(bin, n);
    return 0;
}

เอาต์พุต

The bitwise OR of all the binary String of the string array is 011111