পাইথনে অ্যারেতে যেকোনো সাবসেটের বিটওয়াইজ AND ২-এর ঘাত কিনা

একটি অ্যারে nums দেওয়া আছে। যাচাই করতে হবে যে কি কোনো সাবসেট আছে যার বিটওয়াইজ AND ২-এর ঘাত (power of two)।

উদাহরণ

ইনপুট: nums = [22, 25, 9]

আউটপুট: True

ব্যাখ্যা: সাবসেট {22, 9} -> বাইনারি 10110 & 01001 = 10000 (১৬) যা ২^৪।

অ্যালগরিদম

1. প্রতিটি বিট পজিশন (০-৩১) এর জন্য ঐ বিট সেট থাকা সব সংখ্যা নিন।
2. সেগুলোর বিটওয়াইজ AND করুন।
3. ফলাফল ২-এর ঘাত কিনা চেক করুন।

উদাহরণ কোড

MAX = 32

def is_2s_pow(v):
    return v and (v & (v - 1)) == 0

def solve(nums):
    if len(nums) == 1:
        return is_2s_pow(nums[0])
    total = 0
    for i in range(MAX):
        total |= (1 << i)
    for i in range(MAX):
        ret = total
        for x in nums:
            if x & (1 << i):
                ret &= x
        if is_2s_pow(ret):
            return True
    return False

nums = [22, 25, 9]
print(solve(nums))  # Output: True

ইনপুট

[22, 25, 9]

আউটপুট

True