मान लीजिए हमारे पास nums नामक संख्याओं की एक सरणी है। हमें जांचना है कि क्या nums के किसी उपसमुच्चय का बिटवाइज AND 2 की घात है या नहीं।
उदाहरण के लिए, यदि nums = [22, 25, 9] है, तो आउटपुट True होगा, क्योंकि उपसमुच्चय {22, 9} का बाइनरी रूप {10110, 1001} है और इनका AND 10000 = 16 है जो 2 की घात है।
हल करने का तरीका
- MAX := 32 (अधिकतम 32 बिट संख्याएं मानकर)
- यदि सरणी का आकार 1 है, तो जांचें कि वह संख्या 2 की घात है या नहीं
- total := 0, सभी 32 बिट्स के लिए total = total OR 2^i करें
- प्रत्येक बिट स्थिति i के लिए:
- ret := total
- प्रत्येक संख्या j के लिए: यदि nums[j] में i-वां बिट सेट है, तो ret = ret AND nums[j]
- यदि ret 2 की घात है, तो True लौटाएं
- False लौटाएं
उदाहरण
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 = total | (1 << i)
for i in range(MAX):
ret = total
for j in range(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
