C++で2つの行列を等しくするための変換の数を見つけます

この問題では、同じサイズの2つの行列mat1[][]とmat2[][]が与えられます。私たちの仕事は、2つの行列を等しくするための変換の数を見つけることです。

変換1の行列は-

• 2つの行列の任意の行列を選択します。

• 行列から行または列を選択します

• 選択した行または列のすべての要素に1を追加します。

問題を理解するために例を見てみましょう

入力

mat1[][] = {{1 2}
{2 1}}
mat1[][] = {{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