इस समस्या में, हमें आकार mXn का एक पूर्णांक मानों का मैट्रिक्स mat दिया गया है। हमारा कार्य मैट्रिक्स में समान आयताकार योग वाले सेल्स प्रिंट करने का प्रोग्राम बनाना है।
समस्या विवरण: हम मैट्रिक्स में एक सेल ढूंढेंगे जैसे कि उस सेल से शुरू और समाप्त होने वाले सब-मैट्रिक्स का योग शेष सभी तत्वों के योग के बराबर है।
एक सेल के लिए मैट्रिक्स (a, b) का योग सब-मैट्रिक्स mat[0][0] से mat[a][b] और mat[a][b] से mat[m][n] का योग शेष सभी तत्वों के योग के बराबर है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: mat[][] = {{5, 0, 2, 7}, {3, 0, 1, 0}, {1, 4, 1, 3}, {10, 0, 2, 1}}
आउटपुट: (2, 1)
व्याख्या:
तत्व (2,1) के लिए (0-आधारित इंडेक्सिंग):
सबमैट्रिक्स1 है - {{5, 0}, {3, 0}, {1, 4}} (शीर्ष-बाएं से (2,1) तक)
सबमैट्रिक्स2 है - {{4, 1, 3}, {0, 2, 1}} ((2,1) से नीचे-दाएं तक)
योग = 5+0+3+0+1+4 + 4+1+3+0+2+1 = 24
शेष तत्वों का योग = 2+7+1+0+10 = 20
नोट: मूल उदाहरण में आउटपुट (2,1) दिया गया था लेकिन गणना में विसंगति है। सही आउटपुट (1,1) और (2,1) दोनों हैं जैसा कि प्रोग्राम आउटपुट दिखाता है।
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें 2 सहायक सब-मैट्रिक्स बनाने की आवश्यकता है, aux1[m][n] और aux2[m][n]। aux1[i][j] (0,0) से (i,j) तक के सभी तत्वों का योग स्टोर करेगा और aux2[i][j] (i,j) से (n,m) तक के सभी तत्वों का योग स्टोर करेगा। फिर हम दोनों योगों को जोड़ेंगे और mat(i,j) घटाएंगे क्योंकि यह दो बार आएगा।
फिर हम इस योग की तुलना मैट्रिक्स के सभी तत्वों के योग से करेंगे। यदि सेल पर योग मैट्रिक्स के योग का आधा है। तो वह सेल परिणाम है, और हम इसे प्रिंट करेंगे।
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream>
using namespace std;
#define R 4
#define C 4
void findCellWithSameRectSum(int mat[R][C]) {
int m = R, n = C;
int aux1[m][n], aux2[m][n];
int matSum = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
aux2[i][j] = aux1[i][j] = mat[i][j];
matSum += mat[i][j];
}
}
for (int i = 1; i < m; i++) {
aux1[i][0] += aux1[i-1][0];
aux2[m-i-1][n-1] += aux2[m-i][n-1];
}
for (int j = 1; j < n; j++) {
aux1[0][j] += aux1[0][j-1];
aux2[m-1][n-j-1] += aux2[m-1][n-j];
}
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++) {
aux1[i][j] += aux1[i-1][j] + aux1[i][j-1] - aux1[i-1][j-1];
aux2[m-i-1][n-j-1] += aux2[m-i][n-j-1] + aux2[m-i-1][n-j] - aux2[m-i][n-j];
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matSum == 2 * (aux1[i][j] + aux2[i][j] - mat[i][j]))
cout << "(" << i << ", " << j << ")\t";
}
int main() {
int mat[R][C] = {{5, 0, 2, 7},
{3, 0, 1, 0},
{1, 4, 1, 3},
{10, 0, 2, 1}};
cout << "मैट्रिक्स में समान आयताकार योग वाले सेल्स हैं:\n";
findCellWithSameRectSum(mat);
return 0;
}
आउटपुट
मैट्रिक्स में समान आयताकार योग वाले सेल्स हैं: (1, 1) (2, 1)
एल्गोरिथ्म विश्लेषण
- समय जटिलता: O(m × n)
- स्पेस जटिलता: O(m × n) - दो सहायक मैट्रिक्स के लिए
- तकनीक: 2D प्रीफिक्स सम (सम्मिश्र प्रीफिक्स सम)
मुख्य सूत्र
सेल (i,j) के लिए: कुल_योग = aux1[i][j] + aux2[i][j] - mat[i][j]
शर्त: कुल_योग == matSum / 2 (यानी 2 × कुल_योग == matSum)
