মান লেযিয়ে একটি নন-নেগেটিভ পূর্ণসংখ্যা অ্যারে A দেওয়া আছে। প্রতিটি (contiguous) সাবঅ্যারে B = [A[i], A[i+1], ..., A[j]] (i <= j) এর জন্য, B-এর সব এলিমেন্টের বিটওয়াইজ OR করলে ফলাফল পাওয়া যাবে A[i] | A[i+1] | ... | A[j]। সম্ভাব্য ফলাফলগুলোর সংখ্যা খুঁজে বের করতে হবে (একাধিকবার হলে একবারই কাউন্ট হবে)। ইনপুট [1,1,2] হলে ফলাফল ৩। সাবঅ্যারে: [1], [1], [2], [1,1], [1,2], [1,1,2], ফলাফল: 1,1,2,1,3,3 - তিনটি ডISTINCT ফলাফল।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
ret এবং curr2 নামে দুটি সেট তৈরি করুন
i = 0 থেকে A.size()-1 পর্যন্ত লুপ চালান
curr1 নামে একটি সেট তৈরি করুন, A[i] ইনসার্ট করুন
curr2-এর প্রতিটি এলিমেন্ট e-এর জন্য - curr1-এ (e | A[i]) ইনসার্ট করুন
curr1-এর প্রতিটি এলিমেন্ট e-এর জন্য - ret-এ e ইনসার্ট করুন
curr2 := curr1
ret.size() রিটার্ন করুন
উদাহরণ
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
#include <bits/stdc++.h> using namespace std; class Solution { public: int subarrayBitwiseORs(vector<int>& A) { unordered_set <int> ret; unordered_set <int> curr2; for(int i = 0; i < A.size(); i++){ unordered_set <int> curr1; curr1.insert(A[i]); unordered_set<int>::iterator it = curr2.begin(); while(it != curr2.end()){ curr1.insert(*it | A[i]); it++; } it = curr1.begin(); while(it != curr1.end()){ ret.insert(*it); it++; } curr2 = curr1; } return ret.size(); } }; main(){ vector<int> v = {1,1,2}; Solution ob; cout << (ob.subarrayBitwiseORs(v)); }ইনপুট
[1,1,2]
আউটপুট
3
