পাইথনে বিটওয়াইজ এবং যেকোনো সাবসেটের পাওয়ার দুই কিনা তা পরীক্ষা করুন

ধরুন আমাদের কাছে সংখ্যার একটি অ্যারে আছে যাকে nums বলা হয়। আমাদের পরীক্ষা করতে হবে যে সংখ্যার এমন কোনো উপসেট আছে কি না যার বিটওয়াইজ AND দুটির শক্তি বা না।

সুতরাং, যদি ইনপুটটি nums =[22, 25, 9] এর মত হয়, তাহলে আউটপুটটি True হবে, একটি উপসেট হিসাবে {22, 9} বাইনারি ফর্ম হল {10110, 1001} এই দুটির মধ্যে AND হল 10000 =16 যা 2 এর শক্তি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• MAX :=32 বিবেচনা করে সর্বাধিক 32 বিট সংখ্যা রয়েছে
• একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি সংখ্যা লাগবে
• যদি সংখ্যার আকার 1 হয়, তাহলে
  • সংখ্যা[0] এর ক্ষমতা 2 হলে সত্য প্রত্যাবর্তন করুন, অন্যথায় মিথ্যা
• মোট :=0
• আমি 0 থেকে MAX - 1 রেঞ্জের জন্য, কর
  • মোট :=মোট বা 2^i
• আমি 0 থেকে MAX - 1 রেঞ্জের জন্য, কর
  • ret :=মোট
  j-এর জন্য 0 থেকে সংখ্যার আকারের মধ্যে,
  করুন
  • যদি সংখ্যা[j] AND (2^i) অ-শূন্য হয়, তাহলে
    • ret :=ret AND nums[j]
  • যদি ret এর শক্তি 2 হয়, তাহলে
    • সত্য ফেরান
• মিথ্যে ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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(0, MAX):
      total = total | (1 << i)
   for i in range(0, MAX):
      ret = total
      for j in range(0, len(nums)):
         if nums[j] & (1 << i):
            ret = ret & nums[j]
      if is_2s_pow(ret):
         return True
   return False
nums = [22, 25, 9]
print(solve(nums))

ইনপুট

[22, 25, 9]

আউটপুট

True