ตัวเลขที่เป็นระดับบิตและอย่างน้อยหนึ่งอาร์เรย์ย่อยที่ไม่ว่างเปล่าโดยใช้ C++

เพื่อแก้ปัญหาที่เราได้รับอาร์เรย์ และเราจำเป็นต้องค้นหาจำนวนเต็มที่เป็นไปได้ทั้งหมดซึ่งเป็นระดับบิตและอย่างน้อยหนึ่งอาร์เรย์ย่อยที่ไม่ว่างเปล่า เช่น −

Input : nums[ ] = { 3, 5, 1, 2, 8 }
Output : { 2, 5, 0, 3, 8, 1 }
Explanation:
2 is the bitwise AND of subarray {2},
5 is the bitwise AND of subarray {5},
0 is the bitwise AND of subarray {1, 2}, {2, 8} and {1, 2, 8},
3 is the bitwise AND of subarray {3},
8 is the bitwise AND of subarray {8},
1 is the bitwise AND of subarray {1}, {3, 5} and {3, 5, 1}.

Input : nums[ ] = { 2, 6, 3, 8, 1 }
Output: { 1, 8, 3, 6, 2, 0 }

แนวทางในการหาแนวทางแก้ไข

แนวทางง่ายๆ ที่สามารถนำไปใช้ได้คือ

• ค้นหาอาร์เรย์ย่อยที่ไม่ว่างเปล่าที่เป็นไปได้ทั้งหมด

• ขณะสำรวจผ่านอาร์เรย์ ให้คำนวณระดับบิต AND ของแต่ละองค์ประกอบในอาร์เรย์ย่อย

• เพื่อหลีกเลี่ยงค่าที่ซ้ำกัน ให้เก็บผลลัพธ์ทั้งหมดไว้ในชุด

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] ={ 2, 6, 3, 8, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    // Declaring set to store result of each AND operation.
    unordered_set<int> result;
    int val;
    // nested loops to traverse through all the possible non empty subarrays.
    for (int i = 0; i < n; ++i){
        for (int j = i, val = INT_MAX; j < n; ++j){
            val = val & arr[j];
            // storing result of AND operation
            result.insert(val);
        }
    }
    cout << "All possible numbers are: ";
    // printing all the values of set.
    for (auto i = result.begin(); i != result.end();i++)
        cout << *i << " ";
    return 0;
}

ผลลัพธ์

All possible numbers are: 1 8 3 6 0 2

คำอธิบายของโค้ดด้านบน

• ประกาศตั้งค่าให้เก็บผลลัพธ์ทั้งหมดของการดำเนินการ AND

• การเริ่มต้นตัวแปร 'val' ด้วย INT_MAX เนื่องจากเราจำเป็นต้องดำเนินการ AND โดยตั้งค่าบิตทั้งหมดเป็น 1

• วงในเพื่อผ่านอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมดจากดัชนี ith

• การคำนวณและการทำงานของแต่ละองค์ประกอบด้วยกันและกับตนเองและเก็บไว้ในชุดผลลัพธ์

• การพิมพ์ค่าทั้งหมดของชุดผลลัพธ์

บทสรุป

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