पायथन में k-वें सबसे बड़े XOR कोऑर्डिनेट मान को खोजने का प्रोग्राम

मान लीजिए हमारे पास एक m x n मैट्रिक्स है। और एक मान k। यहां मैट्रिक्स के कोऑर्डिनेट (a, b) का मान उन सभी matrix[i, j] का XOR है जहां i रेंज (0 से a) में है और j रेंज (0 से b) में है। हमें मैट्रिक्स के सभी कोऑर्डिनेट्स के k-वें सबसे बड़े मान (1-इंडेक्स्ड) को ढूंढना है।

उदाहरण के लिए, यदि इनपुट है:

और k = 1, तो आउटपुट 7 होगा क्योंकि कोऑर्डिनेट (0,1) का मान 5 XOR 2 = 7 है, और यह सबसे बड़ा है।

हल करने के चरण

1. m := पंक्ति संख्या, n := कॉलम संख्या
2. i को 0 से m - 1 तक लूप चलाएं:
   • j को 0 से n - 1 तक लूप चलाएं:
     • यदि j नॉन-जीरो है, तो matrix[i][j] := matrix[i][j] XOR matrix[i][j-1]
3. seen := एक नया मैप
4. count := 0
5. i को 0 से n - 1 तक लूप चलाएं:
   • j को 0 से m - 1 तक लूप चलाएं:
     • यदि j नॉन-जीरो है, तो matrix[j][i] := matrix[j][i] XOR matrix[j-1][i]
     • seen[matrix[j][i]] = (1 + seen[matrix[j][i]] यदि संभव हो अन्यथा 1)
     • count := count + 1
     • यदि count > k, तो:
       • min_value := seen का न्यूनतम
       • seen[min_value] := seen[min_value] - 1
       • यदि seen[min_value] == 0, तो seen से min_value-वां एलिमेंट हटाएं।
6. seen का न्यूनतम वापस करें।

उदाहरण

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

def solve(matrix, k):
    m, n = len(matrix), len(matrix[0])
    for i in range(m):
        for j in range(n):
            if j:
                matrix[i][j] ^= matrix[i][j-1]
    seen = {}
    count = 0
    for i in range(n):
        for j in range(m):
            if j:
                matrix[j][i] ^= matrix[j-1][i]
            seen[matrix[j][i]] = seen.get(matrix[j][i], 0) + 1
            count += 1
            if count > k:
                min_value = min(seen)
                seen[min_value] -= 1
                if not seen[min_value]:
                    seen.pop(min_value)
    return min(seen)

matrix = [[5,2],[1,6]]
k = 1
print(solve(matrix, k))

इनपुट

[[5,2],[1,6]], 1

आउटपुट

7