मान लीजिए हमारे पास एक द्वि-आयामी मैट्रिक्स A है जहां प्रत्येक मान 0 या 1 है। यहां एक चाल में किसी भी पंक्ति या स्तंभ को चुनना, और उस पंक्ति या स्तंभ में प्रत्येक मान को टॉगल करना शामिल है: सभी 0s को 1s में, और सभी 1s को 0s में बदलना। अब किसी भी संख्या में चालें बनाने के बाद, इस मैट्रिक्स की प्रत्येक पंक्ति को एक बाइनरी संख्या के रूप में व्याख्या किया जाता है, और मैट्रिक्स का स्कोर इन संख्याओं का योग होता है। हमारा कार्य उच्चतम संभव स्कोर खोजना है।
उदाहरण के लिए, यदि इनपुट मैट्रिक्स है:
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
समाधान दृष्टिकोण
n := पंक्ति संख्या, m := स्तंभ संख्या
ret := n × 2^(m-1) (पहला स्तंभ हमेशा 1 हो सकता है)
j को 1 से m-1 तक: cnt = गिनती जहां A[i][j] == A[i][0]
temp = 2^(m-j-1) × max(cnt, n-cnt)
ret += temp
ret लौटाएं
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int matrixScore(vector<vector<int>>& A) {
int n = A.size();
int m = A[0].size();
int ret = (1 << (m - 1)) * n;
for(int j = 1; j < m; j++){
int cnt = 0;
for(int i = 0; i < n; i++){
cnt += (A[i][j] == A[i][0]);
}
int temp = ((1 << (m - (j + 1))) * max(cnt, n - cnt));
ret += temp;
}
return ret;
}
};
int main(){
vector<vector<int>> v = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
Solution ob;
cout << (ob.matrixScore(v));
return 0;
}
इनपुट
[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
आउटपुट
39