इनपुट के रूप में एक पंक्ति x col मैट्रिक्स को देखते हुए। लक्ष्य मैट्रिक्स [पंक्ति] [col] के भीतर सभी सबमैट्रिस को ढूंढना है, जैसे कि उस सबमैट्रिक्स के तत्वों का योग पूर्णांक k से विभाज्य है।
यदि मैट्रिक्स मैट[3][3] है और k 4 है तो सबमैट्रिस नीचे दिखाए गए अनुसार होंगे:-
आइए उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - मैट्रिक्स[3][3] ={ {1,1,1}, {2,2,2}, {3,3,3} } k=4
आउटपुट - योग विभाज्य 'k' वाले उप-मैट्रिस की संख्या हैं:4
स्पष्टीकरण - सबमैट्रिस ऊपर दिखाए गए अनुसार होंगे।
इनपुट - मैट्रिक्स[3][3] ={ {1,1,1}, {2,2,2}, {3,3,3} } k=12
आउटपुट - योग विभाज्य 'k' वाले उप-मैट्रिस की संख्या हैं:4
स्पष्टीकरण - सबमैट्रिस नीचे दिखाए गए अनुसार होंगे:-
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम मैट्रिक्स को बाएं से दाएं और बाएं और दाएं कॉलम की प्रत्येक जोड़ी के लिए, सबमैट्रिक्स के तत्वों को एरे एआर [] में जोड़ देंगे और अलग से इसके तत्वों और सबएरे के योग की गणना करेंगे, जो कि के द्वारा विभाज्य है।
फ़ंक्शन check_val () एक सरणी लेता है जिसमें सबमैट्रिक्स के तत्व 1D सरणी के रूप में होते हैं। अब संचयी योगों की गणना करें और शेषफलों को k से जांचें और शेषफलों की आवृत्ति को arr_2[] में संग्रहित करें।
- मैट्रिक्स[पंक्ति][col] और पूर्णांक k को इनपुट के रूप में लें।
- फ़ंक्शन check_val(int arr[], int size, int k) सबमैट्रिस के तत्वों की गिरफ्तारी [] लेता है और एआर के भीतर सभी सबएरे की गिनती देता है जिसमें के द्वारा विभाज्य योग होता है
- वेरिएबल काउंट और टेम्परेचर को 0 के रूप में लें।
- के साथ संचयी योगों के शेष की आवृत्तियों को संग्रहीत करने के लिए arr_2[] सरणी लें।
- लूप के लिए i=0 से i<आकार का उपयोग करके संचयी योगों की गणना करें। arr_2[((temp% k) + k) % k]++ (ऋणात्मक योग के लिए दो बार मॉड लें) का उपयोग करके प्रत्येक arr[i] को अस्थायी और शेष की वृद्धि आवृत्ति में जोड़ें।
- फिर से लूप ट्रैवर्स फ़्रीक्वेंसी एरे का उपयोग करना arr_2[] और प्रत्येक मान के लिए>1 arr_2[i] * (arr_2[i] - 1)) / 2 जोड़ें ताकि सभी सबएरे की गिनती संभव हो सके।
- अंत में गिनने के लिए arr_2[0] जोड़ें।
- फ़ंक्शन मैट्रिक्स_डिविज़िबल (इंट मैट्रिक्स [पंक्ति] [कॉल], इंट साइज़, इंट के) एक इनपुट सबमैट्रिक्स लेता है और के द्वारा विभाज्य योग वाले सभी सबमैट्रिस की गिनती देता है।
- प्रारंभिक गणना 0 के रूप में लें।
- एक अस्थायी सरणी को गिरफ्तार करें [आकार]।
- लूप के लिए दो का उपयोग करके बाएँ स्तंभ अनुक्रमणिका i और दाएँ स्तंभ अनुक्रमणिका j सेट करें।
- गिरफ्तारी [अस्थायी] + =मैट्रिक्स [अस्थायी] [जे] के रूप में तत्वों के योग की गणना करें।
- गिरफ्तारी में उपसरणियों की संख्या के लिए [] गिनने के लिए check_val(arr, size, k) जोड़ें।
- लूप के लिए सभी के अंत में, परिणाम के रूप में वापसी की गणना करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define row 10
#define col 10
int check_val(int arr[], int size, int k) {
int count = 0;
int temp = 0;
int arr_2[k];
memset(arr_2, 0, sizeof(arr_2));
for (int i = 0; i < size; i++) {
temp = temp + arr[i];
arr_2[((temp % k) + k) % k]++;
}
for (int i = 0; i < k; i++) {
if (arr_2[i] > 1) {
count += (arr_2[i] * (arr_2[i] - 1)) / 2;
}
}
count = count + arr_2[0];
return count;
}
int matrix_divisible(int matrix[row][col], int size, int k) {
int count = 0;
int arr[size];
for (int i = 0; i < size; i++) {
memset(arr, 0, sizeof(arr));
for (int j = i; j < size; j++) {
for (int temp = 0; temp < size; ++temp) {
arr[temp] += matrix[temp][j];
}
count = count + check_val(arr, size, k);
}
}
return count;
}
int main() {
int matrix[row][col] = {{2,4,-1},{6,1,-9},{2,2, 1}};
int size = 3, k = 4;
cout << "Count of sub-matrices having sum divisible ‘k’ are: " << matrix_divisible(matrix, size, k);
return 0;
} यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा
आउटपुट
Count of sub-matrices having sum divisible 'k' are: 7