संख्याओं की सूची nums और मान k दिया गया है। k बार ऑपरेशन करें: कोई संख्या चुनें, उसके बाइनरी प्रतिनिधित्व में एक 0 बिट को 1 में बदलें। सभी संख्याओं के न्यूनतम संभव योग को वापस करें (मॉड्यूलो 10⁹+7)।
उदाहरण
इनपुट: nums = [4, 7, 3], k = 2
बाइनरी: 4=100, 7=111, 3=011
आउटपुट: 17
व्याख्या: 4 के दो 0 बिट्स (पोजीशन 0 और 1) को 1 बनाएं → 111 (7)। नया योग = 7 + 7 + 3 = 17।
मुख्य अंतर्दृष्टि
न्यूनतम योग वृद्धि के लिए, सबसे कम महत्वपूर्ण 0 बिट्स (LSB से शुरू) को 1 में बदलें। प्रत्येक बिट पोजीशन i के लिए, गिनें कि कितनी संख्याओं में उस पोजीशन पर 0 है। वहां बिट सेट करने से योग में 2^i जुड़ता है।
एल्गोरिदम
ans = 0,i = 0(बिट पोजीशन)।k > 0रहते:- प्रत्येक
ninnumsके लिए:- यदि
(n >> i) & 1 == 0(i-वां बिट 0 है): ans += 1 << ik -= 1- यदि
k == 0: ब्रेक
- यदि
i += 1
- प्रत्येक
(ans + sum(nums)) % (10**9 + 7)वापस करें।
पायथन कार्यान्वयन
class Solution:
def solve(self, nums, k):
MOD = 10**9 + 7
ans = 0
i = 0
while k:
for n in nums:
if ((n >> i) & 1) == 0:
ans += 1 << i
k -= 1
if k == 0:
break
i += 1
return (ans + sum(nums)) % MOD
# परीक्षण
ob = Solution()
print(ob.solve([4, 7, 3], 2)) # 17
print(ob.solve([1, 2, 3], 3)) # 1+2+3 + (1+2+1) = 10?
समय जटिलता
- O(32 × n) = O(n) क्योंकि पूर्णांक 32-बिट हैं (अधिकतम 32 बिट पोजीशन जांचनी पड़ती हैं)।
- स्थान: O(1)।
नोट
यदि k बहुत बड़ा है (सभी 0 बिट्स भरने से अधिक), तो लूप सभी बिट्स को 1 से भर देगा। मॉड्यूलो ऑपरेशन अंत में लागू होता है।