이 문제에서는 같은 크기의 두 행렬 mat1[][]과 mat2[][]가 주어집니다. 우리의 임무는 두 행렬을 동일하게 만들기 위한 변환의 수를 찾는 것입니다.
변환 1 행렬은 -
-
두 행렬 중 아무 행렬이나 선택하십시오.
-
행렬에서 행 또는 열 선택
-
선택한 행 또는 열의 모든 요소에 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
효율적인 접근
이 문제에 대한 보다 효과적인 해결책은 악수 공식을 사용하는 것입니다.
배열의 모듈로에서 0과 1의 발생을 계산하기 위해 temp[] 배열을 만들 것입니다. 그런 다음 카운트 값을 반환합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#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