इस समस्या में, हमें पूर्णांक मानों की एक 2D सरणी दी जाती है mat[][]। हमारा काम मैट के प्रीफ़िक्स सम मैट्रिक्स को प्रिंट करना है।
उपसर्ग योग मैट्रिक्स: मैट्रिक्स का प्रत्येक तत्व इसके ऊपर और बाईं ओर के तत्वों का योग है। यानी
prefixSum[i][j] = mat[i][j] + mat[i-1][j]...mat[0][j] + mat[i][j-1] +... mat[i][0].
आइए समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: arr =[ [4 6 1] [5 7 2] [3 8 9] ] Output:[ [4 10 11] [9 22 25] [12 33 45] ]
इस समस्या को हल करने के लिए, एक सरल उपाय है, सभी तत्वों को i,j स्थिति तक ट्रेस करके और उन्हें जोड़कर प्रीफ़िक्ससम का पता लगाना। लेकिन यह सिस्टम के लिए थोड़ा जटिल है।
एक अधिक प्रभावी समाधान प्रीफ़िक्ससम मैट्रिक्स के तत्वों के मूल्यों को खोजने के लिए सूत्र का उपयोग करना होगा।
ij स्थिति में तत्व के लिए सामान्य सूत्र है
prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]
कुछ विशेष मामले हैं
For i = j = 0, prefixSum[i][j] = a[i][j] For i = 0 and j > 0, prefixSum[i][j] = prefixSum[i][j-1] + a[i][j] For i > 0 and j = 0, prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]
हमारे समाधान के कार्यान्वयन को दिखाने के लिए कोड
उदाहरण
#include <iostream>
using namespace std;
#define R 3
#define C 3
void printPrefixSum(int a[][C]) {
int prefixSum[R][C];
prefixSum[0][0] = a[0][0];
for (int i = 1; i < C; i++)
prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];
for (int i = 0; i < R; i++)
prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++)
prefixSum[i][j]=prefixSum[i- 1][j]+prefixSum[i][j- 1]-prefixSum[i- 1][j- 1]+a[i][j];
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout<<prefixSum[i][j]<<"\t";
cout<<endl;
}
}
int main() {
int mat[R][C] = {
{ 1, 2, 3},
{ 4, 5, 6},
{ 7, 8, 9}
};
cout<<"The prefix Sum Matrix is :\n";
printPrefixSum(mat);
return 0;
} आउटपुट
The prefix Sum Matrix is : 1 3 6 5 12 21 12 27 45