Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में 0 बिट्स को 1 में बदलकर न्यूनतम संभव योग ढूंढने का प्रोग्राम

संख्याओं की सूची 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 जुड़ता है।

एल्गोरिदम

  1. ans = 0, i = 0 (बिट पोजीशन)।
  2. k > 0 रहते:
    • प्रत्येक n in nums के लिए:
      • यदि (n >> i) & 1 == 0 (i-वां बिट 0 है):
        • ans += 1 << i
        • k -= 1
        • यदि k == 0: ब्रेक
    • i += 1
  3. (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 से भर देगा। मॉड्यूलो ऑपरेशन अंत में लागू होता है।

  1. पायथन प्रोग्राम: लिस्ट का संचयी योग ज्ञात करें पायथन प्रोग्राम: लिस्ट का संचयी योग ज्ञात करें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक लिस्ट दी गई है, हमें संचयी योग के साथ एक लिस्ट बनानी है। उदाहरण # संचयी योग def Cumulative(l): new = [] cumsum = 0 for element in l: cumsum += element new.append(cumsum) return new # ड्राइवर

  1. पायथन प्रोग्राम: लिस्ट में एलिमेंट्स का योग ढूंढें पायथन प्रोग्राम: लिस्ट में एलिमेंट्स का योग ढूंढें

    इस लेख में, हम दिए गए प्रॉब्लम स्टेटमेंट को हल करने के समाधान और दृष्टिकोण के बारे में सीखेंगे। प्रॉब्लम स्टेटमेंट इनपुट के रूप में एक लिस्ट दिए जाने पर, हमें दी गई लिस्ट का योग निकालने की आवश्यकता है। यहां हमारे पास दो दृष्टिकोण हैं: बिल्ट-इन फंक्शन का उपयोग करना और ब्रूट-फोर्स दृष्टिकोण का उपयोग

  1. - Python में संख्याओं की सूची का योग कैसे खोजें?

    Python में सूची के संख्याओं का योग Python का बिल्ट-इन फ़ंक्शन sum() सूची या टपल जैसे इटरेबल ऑब्जेक्ट में संख्याओं का योग लौटाता है। यह दो आर्गुमेंट्स लेता है, प्रारंभिक मान जो वैकल्पिक है और डिफ़ॉल्ट रूप से 0 है और इटरेबल ऑब्जेक्ट। उदाहरण >>> l1 = [10, 20, 30, 40, 50] >>> ttl = s