इस समस्या में, हमें समान आकार के दो मैट्रिक्स mat1[][] और mat2[][] दिए जाते हैं। हमारा कार्य दो मैट्रिक्स को बराबर बनाने के लिए आवश्यक परिवर्तनों की संख्या ढूंढना है।
मैट्रिक्स पर परिवर्तन हैं -
दोनों मैट्रिक्स में से किसी एक को चुनें।
मैट्रिक्स से एक पंक्ति या स्तंभ चुनें।
चुनी गई पंक्ति या स्तंभ के सभी तत्वों में 1 जोड़ें।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
mat1[][] = {{1 2} {2 1}} mat2[][] = {{2 3} {4 3}}आउटपुट
3
व्याख्या
1 2 => 2 2 => 2 3 => 2 3 2 1 => 3 1 => 3 2 => 4 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 teo maxtrces equal are "<<countTransformationReq(mat1, mat2, 2, 2) ; return 0; }आउटपुट
The number of transformation to make the teo maxtrces equal are 3
कुशल दृष्टिकोण
इस समस्या का एक अधिक प्रभावी समाधान हैंडशेक फॉर्मूला का उपयोग करना है।
हम एक temp[] सरणी बनाएंगे जो सरणी के मॉड्यूलो में 0 और 1 की घटनाओं को गिनेगा। और फिर गिनती मान वापस करेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#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
