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

पायथन में सभी खंडों का XOR शून्य करने का प्रोग्राम


मान लीजिए हमारे पास nums नामक एक सरणी और एक मान k है। खंड [left, right] (left ≤ right) का XOR उन सभी तत्वों का XOR है जिनके इंडेक्स left और right के बीच हैं (सम्मिलित)।

हमें सरणी में बदलने के लिए न्यूनतम तत्वों की संख्या ज्ञात करनी है ताकि आकार k के सभी खंडों का XOR शून्य के बराबर हो।

उदाहरण के लिए, यदि इनपुट nums = [3,4,5,2,1,7,3,4,7], k = 3 है, तो आउटपुट 3 होगा क्योंकि हम इंडेक्स 2, 3, 4 पर तत्वों को संशोधित करके सरणी को [3,4,7,3,4,7,3,4,7] बना सकते हैं।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

  • LIMIT := 1024

  • temp := आकार LIMIT x k की एक सरणी बनाएं और 0 से भरें।

  • nums में प्रत्येक इंडेक्स i और मान x के लिए, temp[i mod k, x] := temp[i mod k, x] + 1 करें।

  • dp := आकार LIMIT की एक सरणी जिसे -2000 से भरें।

  • dp[0] := 0

  • temp की प्रत्येक पंक्ति के लिए:

    • maxprev := dp का अधिकतम।

    • new_dp := आकार LIMIT की एक सरणी जिसे maxprev से भरें।

    • पंक्ति में प्रत्येक इंडेक्स i और मान cnt के लिए:

      • यदि cnt > 0, तो dp के प्रत्येक इंडेक्स j और मान prev के लिए:

        • new_dp[i XOR j] := new_dp[i XOR j] और (prev + cnt) का अधिकतम।

    • dp := new_dp

  • nums का आकार - new_dp[0] लौटाएं।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(nums, k):    LIMIT = 2**10    temp = [[0 for _ in range(LIMIT)] for _ in range(k)]    for i,x in enumerate(nums):       temp[i%k][x] += 1 dp = [-2000 for _ in range(LIMIT)] dp[0] = 0 for row in temp: maxprev = max(dp) new_dp = [maxprev for _ in range(LIMIT)] for i,cnt in enumerate(row): if cnt > 0: for j,prev in enumerate(dp): new_dp[i^j] = max(new_dp[i^j], prev+cnt) dp = new_dp return len(nums) - new_dp[0] nums = [3,4,5,2,1,7,3,4,7] k = 3 print(solve(nums, k))

इनपुट

[3,4,5,2,1,7,3,4,7], 3 

आउटपुट

-9

  1. पायथन में भारतीय झंडा बनाने का प्रोग्राम पायथन में भारतीय झंडा बनाने का प्रोग्राम

    ग्राफ बनाने के लिए पायथन की लाइब्रेरीज़ में बहुत व्यापक विशेषताएं हैं जो न केवल हमें चार्ट देती हैं बल्कि झंडे जैसे अन्य डायग्राम बनाने की सुविधा भी देती हैं। उस अर्थ में उन मॉड्यूल्स में एक कलात्मक स्पर्श होता है। इस लेख में हम देखेंगे कि numpy और matplotlib लाइब्रेरीज़ का उपयोग करके भारतीय झंडा कै

  1. - Python प्रोग्राम से डिक्शनरी में सभी आइटम का योग खोजना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक डिक्शनरी दी गई है, और हमें डिक्शनरी में 3 उच्चतम मान प्रिंट करने की आवश्यकता है। समस्या कथन के लिए तीन दृष्टिकोण नीचे दिए गए हैं: दृष्टिकोण 1 - डिक्शनरी पुनरावृत्ति से योग की गणना करना उदाहरण # sum फ़ंक्शन d

  1. - सूची में सभी संख्याओं को गुणा करने का पायथन प्रोग्राम

    समस्या विवरण सबसे पहले हम यूजर इनपुट के लिए 3 सूचियां बनाते हैं। यहां हम ट्रैवर्सल तकनीक का उपयोग करते हैं। उत्पाद के मान को 1 से आरंभ करें, सभी तत्वों को पार करें और सूची के अंत तक एक-एक करके प्रत्येक संख्या को उत्पाद से गुणा करें। उदाहरण इनपुट: A=[5,6,3] आउटपुट: 90 व्याख्या: 5*6*3 एल्गोरिदम सू