ইনপুট হিসাবে একটি সারি x কোল ম্যাট্রিক্স দেওয়া হয়েছে। লক্ষ্য হল ম্যাট্রিক্স[সারি][কল] এর মধ্যে সমস্ত সাবম্যাট্রিক্স খুঁজে বের করা যাতে সেই সাবম্যাট্রিক্সের উপাদানগুলির যোগফল কে পূর্ণসংখ্যা দিয়ে বিভাজ্য হয়।
যদি ম্যাট্রিক্স ম্যাট হয় [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
ব্যাখ্যা - সাবমেট্রিসগুলি নীচে দেখানো হবে:-
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা ম্যাট্রিক্সকে বাম থেকে ডানে অতিক্রম করব এবং বাম এবং ডান কলামগুলির প্রতিটি জোড়ার জন্য, অ্যারে অ্যারেতে সাবম্যাট্রিক্সের উপাদানগুলি যোগ করব এবং আলাদাভাবে এর উপাদানগুলির যোগফল এবং k দ্বারা বিভাজ্য সাবঅ্যারেগুলির যোগফল গণনা করব।
ফাংশন check_val() 1D অ্যারে হিসাবে সাবম্যাট্রিক্সের উপাদান সহ একটি অ্যারে নেয়। এখন ক্রমবর্ধমান যোগফল গণনা করুন এবং অবশিষ্টাংশগুলি কে দিয়ে পরীক্ষা করুন এবং অ্যারে অ্যারে_2[]-এ অবশিষ্টাংশের ফ্রিকোয়েন্সি সংরক্ষণ করুন।
- ইনপুট হিসাবে ম্যাট্রিক্স[সারি][কল] এবং পূর্ণসংখ্যা k নিন।
- ফাংশন check_val(int arr[], int size, int k) সাবমেট্রিসের উপাদানগুলির arr[] নেয় এবং arr-এর মধ্যে থাকা সমস্ত সাবয়ারের গণনা দেয় যেগুলির যোগফল k দ্বারা বিভাজ্য হয়
- ভেরিয়েবল গণনা এবং তাপমাত্রা 0 হিসাবে নিন।
- k এর সাথে ক্রমবর্ধমান সমষ্টির অবশিষ্টাংশের ফ্রিকোয়েন্সি সংরক্ষণের জন্য অ্যারে arr_2[] নিন।
- i=0 থেকে i
- আবার লুপ ট্রাভার্স ফ্রিকোয়েন্সি অ্যারে arr_2[] ব্যবহার করে এবং প্রতিটি মানের জন্য> 1 যোগ করুন arr_2[i] * (arr_2[i] - 1)) / 2 সম্ভাব্য সমস্ত সাবয়ারের গণনা হিসাবে গণনা করতে।
- শেষে গণনা করতে arr_2[0] যোগ করুন।
- ফাংশন matrix_divisible(int matrix[row][col], int size, int k) একটি ইনপুট সাবম্যাট্রিক্স নেয় এবং k দ্বারা বিভাজ্য সমষ্টি সহ সমস্ত সাবম্যাট্রিক্সের গণনা প্রদান করে।
- প্রাথমিক গণনাকে 0 হিসাবে নিন।
- একটি অস্থায়ী অ্যারে arr[size] নিন।
- লুপের জন্য দুটি ব্যবহার করে বাম কলাম সূচক i এবং ডান কলাম সূচী j সেট করুন।
- এআরআর[temp]+=ম্যাট্রিক্স[temp][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
