पायथन में जांचें कि कोई ऐरे ऐसे जोड़ों में विभाजित हो सकता है जिनका योग k से विभाज्य हो

मान लीजिए हमारे पास संख्याओं का एक ऐरे और एक संख्या k है। हमें यह जांचना है कि क्या दिया गया ऐरे ऐसे जोड़ों में विभाजित किया जा सकता है कि प्रत्येक जोड़ी का योग k से विभाज्य हो।

उदाहरण के लिए, यदि इनपुट arr = [5, 15, 6, 9] और k = 7 है, तो आउटपुट True होगा क्योंकि हम (5, 9) और (15, 6) जैसे जोड़े बना सकते हैं।

समाधान दृष्टिकोण

हम प्रत्येक तत्व का k के सापेक्ष शेष (remainder) निकालते हैं। दो संख्याओं का योग k से विभाज्य तभी होगा जब उनके शेषों का योग k हो (या दोनों 0 हों)।

एल्गोरिदम चरण:

1. यदि ऐरे का आकार विषम है, तो False लौटाएं
2. प्रत्येक तत्व के लिए remainder = ((num % k) + k) % k की गणना करें (नकारात्मक संख्याओं को संभालने के लिए)
3. प्रत्येक शेष की आवृत्ति गिनें
4. प्रत्येक शेष r के लिए:
• यदि 2*r == k (यानी r = k/2), तो इसकी आवृत्ति सम होनी चाहिए
• यदि r == 0, तो इसकी आवृत्ति सम होनी चाहिए
• अन्यथा, r की आवृत्ति k-r की आवृत्ति के बराबर होनी चाहिए
5. यदि सभी शर्तें पूरी होती हैं, तो True लौटाएं

पायथन कार्यान्वयन

from collections import defaultdict

def solve(array, k):
    n = len(array)
    if n % 2 != 0:
        return False
    
    occurrences = defaultdict(int)
    for i in range(n):
        remainder = ((array[i] % k) + k) % k
        occurrences[remainder] += 1
    
    for i in range(n):
        remainder = ((array[i] % k) + k) % k
        if 2 * remainder == k:
            if occurrences[remainder] % 2 != 0:
                return False
        elif remainder == 0:
            if occurrences[remainder] & 1:
                return False
        elif occurrences[remainder] != occurrences[k - remainder]:
            return False
    return True

arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))  # True

इनपुट

[5, 15, 6, 9], 7

आउटपुट

True

व्याख्या:

k=7 के लिए शेष:

• 5 % 7 = 5
• 15 % 7 = 1
• 6 % 7 = 6
• 9 % 7 = 2

जोड़े: (5,2) → शेष 5+2=7 ✓, (1,6) → शेष 1+6=7 ✓