Minimum increments required to make the sum of all adjacent matrix elements even
Given a matrix mat[][] of dimensions N × M, the task is to minimize the number of increments of matrix elements required to make the sum of adjacent matrix elements even.
Note: For any matrix element mat[i][j], consider mat[i – 1][j], mat[i+1][j], mat[i][j – 1] and mat[i][j + 1] as its adjacent elements.
Examples:
Input: mat[][] = {{1, 5, 6}, {4, 7, 8}, {2, 2, 3}}
Output: 4
Explanation:
Increase cell mat[0][0] by 1, mat[1][1] by 1, mat[0][1] by 1 and mat[2][2] by 1.
Therefore, total number of increments required is 4. Therefore, modified matrix is {{2, 6, 6}, {4, 8, 8}, {2, 2, 4}} having sum of all adjacent elements even.
Input: mat[][] = {{1, 5, 5}, {5, 5, 5}, {5, 1, 1}}
Output: 0
Approach: The idea to solve the given problem is based on the fact that the sum of two elements is even only if both the numbers are even or odd. Therefore, for the matrix to have the sum of adjacent elements even, all matrix elements should have the same parity, i.e. either all odd or all even.
Therefore, the minimum number of increments required is the minimum of the count of even and odd elements in the given matrix.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int MAX = 500; // Function to find the minimum number // of increments required to make sum of // al adjacent matrix elements even int minOperations( int mat[][MAX], int N) { // Stores the count of odd elements int oddCount = 0; // Stores the count of even elements int evenCount = 0; // Iterate the matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { // If element is odd if (mat[i][j] & 1) { // Increment odd count oddCount++; } // Otherwise else { // Increment even count evenCount++; } } } // Print the minimum of both counts cout << min(oddCount, evenCount); } // Driver Code int main() { int mat[][MAX] = { { 1, 5, 6 }, { 4, 7, 8 }, { 2, 2, 3 } }; int N = sizeof (mat) / sizeof (mat[0]); minOperations(mat, N); return 0; } |
Java
// Java program for the above approach class GFG { static int MAX = 500 ; // Function to find the minimum number // of increments required to make sum of // al adjacent matrix elements even static void minOperations( int mat[][], int N) { // Stores the count of odd elements int oddCount = 0 ; // Stores the count of even elements int evenCount = 0 ; // Iterate the matrix for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { // If element is odd if (mat[i][j] % 2 == 1 ) { // Increment odd count oddCount++; } // Otherwise else { // Increment even count evenCount++; } } } // Print the minimum of both counts System.out.print(Math.min(oddCount, evenCount)); } // Driver Code public static void main(String[] args) { int mat[][] = { { 1 , 5 , 6 }, { 4 , 7 , 8 }, { 2 , 2 , 3 } }; int N = mat.length; minOperations(mat, N); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approach MAX = 500 # Function to find the minimum number # of increments required to make sum of # al adjacent matrix elements even def minOperations(mat, N): # Stores the count of odd elements oddCount = 0 # Stores the count of even elements evenCount = 0 # Iterate the matrix for i in range (N): for j in range (N): # If element is odd if (mat[i][j] & 1 ): # Increment odd count oddCount + = 1 # Otherwise else : # Increment even count evenCount + = 1 # Print the minimum of both counts print ( min (oddCount, evenCount)) # Driver Code if __name__ = = '__main__' : mat = [[ 1 , 5 , 6 ], [ 4 , 7 , 8 ], [ 2 , 2 , 3 ]] N = len (mat) minOperations(mat, N) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG { const int MAX = 500; // Function to find the minimum number // of increments required to make sum of // al adjacent matrix elements even static void minOperations( int [, ] mat, int N) { // Stores the count of odd elements int oddCount = 0; // Stores the count of even elements int evenCount = 0; // Iterate the matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { // If element is odd if ((mat[i, j] & 1) != 0) { // Increment odd count oddCount++; } // Otherwise else { // Increment even count evenCount++; } } } // Print the minimum of both counts Console.Write(Math.Min(oddCount, evenCount)); } // Driver Code public static void Main() { int [, ] mat = { { 1, 5, 6 }, { 4, 7, 8 }, { 2, 2, 3 } }; int N = mat.GetLength(0); minOperations(mat, N); } } // This code is contributed by chitranayal. |
Javascript
<script> // Java script program for the above approach let MAX = 500; // Function to find the minimum number // of increments required to make sum of // al adjacent matrix elements even function minOperations(mat, N) { // Stores the count of odd elements let oddCount = 0; // Stores the count of even elements let evenCount = 0; // Iterate the matrix for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { // If element is odd if (mat[i][j] % 2== 1) { // Increment odd count oddCount++; } // Otherwise else { // Increment even count evenCount++; } } } // Print the minimum of both counts document.write(Math.min(oddCount, evenCount)); } // Driver Code let mat= [ [ 1, 5, 6 ], [ 4, 7, 8 ], [ 2, 2, 3 ] ]; let N = mat.length; minOperations(mat, N); //contributed by bobby </script> |
4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us