इनपुट के रूप में एक row x col मैट्रिक्स दिया गया है। लक्ष्य मैट्रिक्स[row][col] के भीतर उन सभी सबमैट्रिक्स को ढूंढना है जिनके तत्वों का योग पूर्णांक k से विभाज्य है।
यदि मैट्रिक्स mat[3][3] है और k 4 है तो सबमैट्रिक्स नीचे दिखाए अनुसार होंगे:-
उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - matrix[3][3] = { {1,1,1}, {2,2,2}, {3,3,3} } k=4
आउटपुट - योग k से विभाज्य वाले सब-मैट्रिक्स की संख्या: 4
व्याख्या - सबमैट्रिक्स ऊपर दिखाए अनुसार होंगे।
इनपुट - matrix[3][3] = { {1,1,1}, {2,2,2 }, {3,3,3} } k=12
आउटपुट - योग k से विभाज्य वाले सब-मैट्रिक्स की संख्या: 4
व्याख्या - सबमैट्रिक्स नीचे दिखाए अनुसार होंगे:-
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम मैट्रिक्स को बाएं से दाएं पार करेंगे और बाएं और दाएं कॉलम के प्रत्येक जोड़े के लिए, सबमैट्रिक्स के तत्वों को सरणी arr[] में जोड़ेंगे और अलग से उसके तत्वों का योग और k से विभाज्य योग वाले सबएरे की गणना करेंगे।
फ़ंक्शन check_val() सबमैट्रिक्स के तत्वों वाली 1D सरणी के रूप में एक सरणी लेता है। अब संचयी योग की गणना करें और k के साथ शेषफल जांचें और शेषफल की फ्रीक्वेंसी को सरणी arr_2[] में संग्रहीत करें।
- मैट्रिक्स row][col] और पूर्णांक k को इनपुट के रूप में लें।
- फ़ंक्शन check_val(int arr[], int size, int k) सबमैट्रिक्स के तत्वों की सरणी arr[] लेता है और arr के भीतर उन सभी सबएरे की गिनती लौटाता है जिनका योग k से विभाज्य है
- वेरिएबल count और temp को 0 लें।
- संचयी योग के शेषफल की फ्रीक्वेंसी संग्रहीत करने के लिए सरणी arr_2[] लें।
- i=0 से i<size तक for लूप का उपयोग करके संचयी योग की गणना करें। प्रत्येक arr[i] को temp में जोड़ें और शेषफल की फ्रीक्वेंसी को arr_2[((temp % k) + k) % k]++ का उपयोग करके बढ़ाएं (ऋणात्मक योग के लिए दो बार मॉड लें)।
- फिर से for लूप का उपयोग करके फ्रीक्वेंसी सरणी arr_2[] को पार करें और प्रत्येक मान>1 के लिए arr_2[i] * (arr_2[i] - 1)) / 2 को count में जोड़ें सभी संभावित सबएरे की गिनती के रूप में।
- अंत में count में arr_2[0] जोड़ें।
- फ़ंक्शन matrix_divisible(int matrix[row][col], int size, int k) एक इनपुट सबमैट्रिक्स लेता है और k से विभाज्य योग वाले सभी सबमैट्रिक्स की गिनती लौटाता है।
- प्रारंभिक गिनती 0 लें।
- एक अस्थायी सरणी arr[size] लें।
- दो for लूप का उपयोग करके बाएं कॉलम इंडेक्स i और दाएं कॉलम इंडेक्स j सेट करें।
- तत्वों के योग की गणना arr[temp]+= matrix[temp][j] के रूप में करें।
- arr[] में सबएरे की संख्या के लिए check_val(arr, size, k) को count में जोड़ें।
- सभी for लूप के अंत में, परिणाम के रूप में count लौटाएं।
उदाहरण
#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
