C++ หาตัวเลขที่เป็น Bitwise AND ของ Sub-Array ที่ไม่ว่างอย่างน้อยหนึ่งชุด

เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์ และต้องหาตัวเลขจำนวนเต็มทั้งหมดที่เป็นไปได้ ซึ่งเป็น Bitwise AND ของ Sub-array ที่ไม่ว่างอย่างน้อยหนึ่งชุด เช่น

Input : nums[ ] = { 3, 5, 1, 2, 8 } Output : { 2, 5, 0, 3, 8, 1 } Explanation: 2 เป็น AND ของ {2}, 5 ของ {5}, 0 ของ {1, 2}, {2, 8}, {1, 2, 8}, 3 ของ {3}, 8 ของ {8}, 1 ของ {1}, {3, 5}, {3, 5, 1}
Input : nums[ ] = { 2, 6, 3, 8, 1 } Output: { 1, 8, 3, 6, 2, 0 }

วิธีการแก้ปัญหา

วิธี Simple Approach ที่สามารถนำมาใช้ได้คือ

• หา Sub-array ที่ไม่ว่างทั้งหมดที่เป็นไปได้
• ขณะวนลูปผ่านอาร์เรย์ คำนวณ Bitwise AND ของแต่ละสมาชิกใน Sub-array
• เพื่อป้องกันค่าซ้ำ เก็บผลลัพธ์ทั้งหมดใน Set

ตัวอย่าง

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

int main(){ 
    int arr[] ={ 2, 6, 3, 8, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    unordered_set<int> result; 
    int val; 
    for (int i = 0; i < n; ++i){ 
        for (int j = i, val = INT_MAX; j < n; ++j){ 
            val = val & arr[j]; 
            result.insert(val); 
        } 
    } 
    cout << "All possible numbers are: "; 
    for (auto i = result.begin(); i != result.end(); i++) 
        cout << *i << " "; 
    return 0; 
}

ผลลัพธ์

All possible numbers are: 1 8 3 6 0 2

คำอธิบายโค้ด

• ประกาศ Set เก็บผลลัพธ์ของแต่ละการ AND
• เริ่มต้นตัวแปร 'val' ด้วย INT_MAX เพราะเราต้องทำ AND กับบิตที่ทั้งหมดเป็น 1
• ลูปในเพื่อไปผ่าน Sub-array ทั้งหมดจากดัชนี i
• คำนวณ AND ของแต่ละสมาชิกกับกันและกับตัวเอง เก็บใน Set result
• พิมพ์ค่าทั้งหมดของ Set result

สรุป

ในบทช่วยสอนนี้ เราอภิบัติวิธีง่ายในการแก้ปัญหานี้ คือ คำนวณ AND ในทุก Sub-array ที่เป็นไปได้ เรายังอภิบัติโปรแกรม C++ เพื่อแก้ปัญหานี้ สามารถเขียนโค้ดนี้ในภาษาอื่น เช่น Java, C, Python ได้ หวังว่าจะเป็นประโยชน์