এই সমস্যায়, আমাদের একই আকারের দুটি ম্যাট্রিক্স mat1[][] এবং mat2[][] দেওয়া আছে। আমাদের কাজ হল দুটি ম্যাট্রিক্স সমান করার জন্য কতগুলো ট্রান্সফরমেশন দরকার তা খুঁজে বের করা।
ম্যাট্রিক্সের ট্রান্সফরমেশন হল:
- দুটি ম্যাট্রিক্স থেকে যেকোনো একটি নির্বাচন করুন।
- ম্যাট্রিক্স থেকে একটি সারি বা কলাম নির্বাচন করুন।
- নির্বাচিত সারি বা কলামের সব এলিমেন্টে ১ যোগ করুন।
উদাহরণ
ইনপুট
mat1[][] = {{1, 2}, {2, 1}}
mat2[][] = {{2, 3}, {4, 3}}
আউটপুট
3
ব্যাখ্যা
১ ২ => ২ ২ => ২ ৩ => ২ ৩ ২ ১ => ৩ ১ => ৩ ২ => ৪ ৩
সমাধানের পদ্ধতি
এই সমস্যার সহজ সমাধান হল ট্রান্সফরমেশন সম্ভব কিনা তা বের করা। এর জন্য আমাদের চেক করতে হবে:
if( mat[i][j] - mat[i][0] - mat[0][j] + mat[0][0] != 0 )
তবে কোনো সমাধান নেই।
যদি ট্রান্সফরমেশন সম্ভব হয়, তবে আমরা সারি ও কলামের জন্য ট্রান্সফরমেশন গণনা করব।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int countTransformationReq(int mat1[][MAX], int mat2[][MAX], int m, int n) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
mat1[i][j] -= mat2[i][j];
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
if (mat1[i][j] - mat1[i][0] - mat1[0][j] + mat1[0][0] != 0)
return -1;
int trxCount = 0;
for (int i = 0; i < n; i++)
trxCount += abs(mat1[i][0]);
for (int j = 0; j < m; j++)
trxCount += abs(mat1[0][j] - mat1[0][0]);
return trxCount;
}
int main() {
int mat1[MAX][MAX] = { {1, 2}, {2, 1} };
int mat2[MAX][MAX] = { {2, 3}, {4, 3} };
cout << "The number of transformation to make the two matrices equal are " << countTransformationReq(mat1, mat2, 2, 2);
return 0;
}
আউটপুট
The number of transformation to make the two matrices equal are 3
দক্ষ পদ্ধতি
এই সমস্যার আরও একটি দক্ষ সমাধান হল হ্যান্ডশেক সূত্র ব্যবহার করা। আমরা একটি টেম্প অ্যারে তৈরি করব ০ এবং ১-এর অকুরেন্স গণনা করার জন্য মডুলো অ্যারেতে। এবং তারপর কাউন্ট ভ্যালু রিটার্ন করব।
প্রোগ্রাম উদাহরণ (অন্য সমস্যা: সম যোগফল ওয়ালা সাবঅ্যারে)
#include <iostream>
using namespace std;
int countEvenSumSubArray(int arr[], int n){
int temp[2] = {1, 0};
int count = 0, sum = 0;
for (int i = 0; i <= n-1; i++){
sum = ((sum + arr[i]) % 2 + 2) % 2;
temp[sum]++;
}
count += (temp[0] * (temp[0] - 1) / 2);
count += (temp[1] * (temp[1] - 1) / 2);
return count;
}
int main(){
int arr[] = {2, 1, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The count of Subarrays with even sum is " << countEvenSumSubArray(arr, n);
return 0;
}
আউটপুট
The count of Subarrays with even sum is 4
