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