मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है। दी गई मैट्रिक्स में किसी भी पंक्ति या स्तंभ के लिए हम सभी बिट्स को फ्लिप कर सकते हैं। यदि हम इन ऑपरेशनों को कितनी भी बार कर सकते हैं, और प्रत्येक पंक्ति को एक बाइनरी संख्या मानते हैं, तो हमें इन संख्याओं से बनने वाले सबसे बड़े योग को ढूंढना है।
उदाहरण के लिए, यदि इनपुट है:
| 0 | 1 | 0 |
| 0 | 0 | 1 |
तो आउटपुट 11 होगा, क्योंकि यदि हम दोनों पंक्तियों को फ्लिप करते हैं तो हमें 101 और 110 मिलते हैं, जिनका योग 5 + 6 = 11 है।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- मैट्रिक्स में प्रत्येक पंक्ति r के लिए, करें
- यदि r[0] 0 के समान है, तो
- i को 0 से r के आकार तक रेंज में, करें
- r[i] := -r[i] + 1
- i को 0 से r के आकार तक रेंज में, करें
- यदि r[0] 0 के समान है, तो
- j को 1 से मैट्रिक्स के स्तंभ आकार तक रेंज में, करें
- cnt := 0
- i को 0 से मैट्रिक्स की पंक्ति संख्या तक रेंज में, करें
- यदि matrix[i, j] 1 है तो cnt := cnt + 1 अन्यथा -1
- यदि cnt < 0, तो
- i को 0 से मैट्रिक्स की पंक्ति आकार तक रेंज में, करें
- matrix[i, j] := -matrix[i, j] + 1
- i को 0 से मैट्रिक्स की पंक्ति आकार तक रेंज में, करें
- ans := 0
- मैट्रिक्स में प्रत्येक पंक्ति r के लिए, करें
- a := 0
- r में प्रत्येक v के लिए, करें
- a := 2 * a + v
- ans := ans + a
- ans लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class Solution: def solve(self, matrix): for r in matrix: if r[0] == 0: for i in range(len(r)): r[i] = -r[i] + 1 for j in range(1, len(matrix[0])): cnt = 0 for i in range(len(matrix)): cnt += 1 if matrix[i][j] else -1 if cnt < 0: for i in range(len(matrix)): matrix[i][j] = -matrix[i][j] + 1 ans = 0 for r in matrix: a = 0 for v in r: a = 2 * a + v ans += a return ans ob = Solution() matrix = [ [0, 1, 0], [0, 0, 1] ] print(ob.solve(matrix))
इनपुट
[[0, 1, 0],[0, 0, 1]]
आउटपुट
11