একটি সমস্যা সমাধান করতে হবে যেখানে একটি অ্যারে দেওয়া আছে, এবং আমাদের সব সম্ভাব্য পূর্ণসংখ্যা বের করতে হবে যেগুলো কমপক্ষে একটি খালি নন (non-empty) সাব-অ্যারে (subarray) এর বিটওয়াইজ AND (bitwise AND) হতে পারে। উদাহরণ −
ইনপুট: nums[] = { 3, 5, 1, 2, 8 } আউটপুট: { 2, 5, 0, 3, 8, 1 } ব্যাখ্যা: 2 হলো {2} সাবঅ্যারের AND, 5 হলো {5}-এর AND, 0 হলো {1, 2}, {2, 8}, {1, 2, 8}-এর AND, 3 হলো {3}-এর AND, 8 হলো {8}-এর AND, 1 হলো {1}, {3, 5}, {3, 5, 1}-এর AND।
ইনপুট: nums[] = { 2, 6, 3, 8, 1 } আউটপুট: { 1, 8, 3, 6, 2, 0 }
একটি সহজ পদ্ধতি (Simple Approach) হলো −
সব সম্ভাব্য নন-এম্পটি সাবঅ্যারে বের করা।
অ্যারে ট্রাভার্স করার সময় প্রতিটি সাবঅ্যারের এলিমেন্টের বিটওয়াইজ AND গণনা করা।
ডুপ্লিকেট (duplicate) ভ্যালু এড়াতে সব ফলাফল সেট (set) এ রাখা।
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = { 2, 6, 3, 8, 1 }; int n = sizeof(arr) / sizeof(arr[0]); // প্রতিটি AND অপারেশনের ফলাফল রাখার সেট 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); // AND ফলাফল সেটে রাখা } } 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
AND অপারেশনের সব ফলাফল রাখার জন্য সেট ডিক্লেয়ার।
'val' ভেরিয়েবল INT_MAX দিয়ে ইনিশিয়ালাইজ কারণ সব বিট ১ থাকা অবস্থায় AND শুরু করতে হবে।
ইননার লুপ: i-তম ইনডেক্স থেকে সব সম্ভাব্য সাবঅ্যারে।
প্রতিটি এলিমেন্টের সাথে AND অপারেশন করে রেজাল্ট সেটে রাখা।
রেজাল্ট সেটের সব ভ্যালু প্রিন্ট।
এই টিউটোরিয়ালে আমরা এই সমস্যা সমাধানের একটি সহজ পদ্ধতি আলোচনা করেছি: প্রতিটি সম্ভাব্য সাবঅ্যারেতে AND অপারেশন গণনা করা। এই সমস্যা সমাধানের C++ প্রোগ্রামও দেওয়া আছে। আপনি এই কোড Java, C, Python ইত্যাদি ভাষায়ও লিখতে পারেন। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।
