Given an integer K and a square matrix mat[][] of size N * N with elements from the range[1, K], the task is to count ways to remove pairs of distinct matrix elements such that remaining elements can be arranged in pairs vertically or horizontally.
Examples:
Input: mat[][] = {{1, 2}, {3, 4}}, K = 4
Output: 4
Explanation:
Remove the row {1, 2}. Therefore, remaining elements are {3, 4}, which can be arranged in a horizontal group of 2.
Similarly, removing pairs (1, 3), (3, 4) and (2, 4) can also form such arrangements.Input: mat[][] = {{1, 2, 3}, {2, 2, 2}, {1, 2, 2}}, K = 3
Output: 0
Approach: The idea is based on the below observations:
- If N is odd, then no matter which pair is removed the remaining matrix can not be covered with the smaller matrices. This is because, upon removal of any pair of the matrix, the remaining elements will be odd, it is not possible to cover them using a 2×1 or 1×2 size matrix.
- For other cases, covering the remaining matrix after removal of a pair (a, b) is only possible if the sum of row index, i and column index, j of a is even and that of b is odd or vice versa.
Follow the steps below to solve the problem:
- If the size of the matrix is odd, then print 0 as there can be no possible arrangements.
- Otherwise, check for the following:
- Initialize a variable ans as 0 to store the number of required pairs.
- Initialize an auxiliary matrix, dp[][] of size K×2, dp[i][0] indicating the number of occurrences of i in the matrix mat[][] whose sum of row index and column index is even, and dp[i][1] indicating the number of occurrences of i in mat[][] whose sum of row index and column index is odd.
- Traverse the matrix mat[][] row-wise using row index i and column index j and if the sum of i and j is even, then increment dp[(mat[i][j] – 1)][0] by 1, else increment dp[(mat[i][j] – 1)][1] by 1.
- Iterate over the range [0, K – 1] using the variable i and nested iterate in the range [i + 1, K – 1] using variable j:
- Add the value of dp[i][0] * dp[j][1] to ans as the value of both block differ and (i + j) and the value of one is odd and (i + j) value of other is even.
- Add the value of dp[i][1] * dp[j][0] to ans as the value of both block differ and (i + j) value of one is even and (i + j) value of other is odd
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach :
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count ways to remove pairs // such that the remaining elements can // be arranged in pairs vertically or horizontally void numberofpairs(vector<vector<int> > v, int k) { // Store the size of matrix int n = v.size(); // If N is odd, then no // such pair exists if (n % 2 == 1) { cout << 0; return; } // Store the number of // required pairs int ans = 0; // Initialize an auxiliary // matrix and fill it with 0s int dp[k][2]; for (int i = 0; i < k; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = 0; } } // Traverse the matrix v[][] for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check if i+j is odd or even if ((i + j) % 2 == 0) // Increment the value // dp[v[i][j]-1][0] by 1 dp[v[i][j] - 1][0]++; else // Increment the value // dp[v[i][j]-1][1] by 1 dp[v[i][j] - 1][1]++; } } // Iterate in range[0, k-1] using i for (int i = 0; i < k; i++) { // Iterate in range[i+1, k-1] using j for (int j = i + 1; j < k; j++) { // Update the ans ans += dp[i][0] * dp[j][1]; ans += dp[i][1] * dp[j][0]; } } // Print the answer cout << ans; } // Driver Code int main() { vector<vector<int> > mat = { { 1, 2 }, { 3, 4 } }; int K = 4; numberofpairs(mat, K); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to count ways to remove pairs // such that the remaining elements can // be arranged in pairs vertically or horizontally static void numberofpairs(int[][] v, int k) { // Store the size of matrix int n = v.length; // If N is odd, then no // such pair exists if (n % 2 == 1) { System.out.println(0); return; } // Store the number of // required pairs int ans = 0; // Initialize an auxiliary // matrix and fill it with 0s int dp[][] = new int[k][2]; for (int i = 0; i < k; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = 0; } } // Traverse the matrix v[][] for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check if i+j is odd or even if ((i + j) % 2 == 0) // Increment the value // dp[v[i][j]-1][0] by 1 dp[v[i][j] - 1][0]++; else // Increment the value // dp[v[i][j]-1][1] by 1 dp[v[i][j] - 1][1]++; } } // Iterate in range[0, k-1] using i for (int i = 0; i < k; i++) { // Iterate in range[i+1, k-1] using j for (int j = i + 1; j < k; j++) { // Update the ans ans += dp[i][0] * dp[j][1]; ans += dp[i][1] * dp[j][0]; } } // Print the answer System.out.println(ans); } // Driver Code public static void main(String[] args) { int[][] mat = { { 1, 2 }, { 3, 4 } }; int K = 4; numberofpairs(mat, K); } } // This code is contributed by susmitakundogoaldanga. |
Python3
# Python3 program for the above approach # Function to count ways to remove pairs # such that the remaining elements can # be arranged in pairs vertically or horizontally def numberofpairs(v, k) : # Store the size of matrix n = len(v) # If N is odd, then no # such pair exists if (n % 2 == 1) : print(0) return # Store the number of # required pairs ans = 0 # Initialize an auxiliary # matrix and fill it with 0s dp = [[0 for i in range(2)] for j in range(k)] for i in range(k) : for j in range(2) : dp[i][j] = 0 # Traverse the matrix v[][] for i in range(n) : for j in range(n) : # Check if i+j is odd or even if ((i + j) % 2 == 0) : # Increment the value # dp[v[i][j]-1][0] by 1 dp[v[i][j] - 1][0] += 1 else : # Increment the value # dp[v[i][j]-1][1] by 1 dp[v[i][j] - 1][1] += 1 # Iterate in range[0, k-1] using i for i in range(k) : # Iterate in range[i+1, k-1] using j for j in range(i + 1, k) : # Update the ans ans += dp[i][0] * dp[j][1] ans += dp[i][1] * dp[j][0] # Print the answer print(ans) # Driver code mat = [ [ 1, 2 ], [ 3, 4 ] ] K = 4numberofpairs(mat, K) # This code is contributed by divyeshrabdiya07. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to count ways to remove pairs // such that the remaining elements can // be arranged in pairs vertically or horizontally static void numberofpairs(List<List<int> > v, int k) { // Store the size of matrix int n = v.Count; // If N is odd, then no // such pair exists if (n % 2 == 1) { Console.Write(0); return; } // Store the number of // required pairs int ans = 0; // Initialize an auxiliary // matrix and fill it with 0s int[,] dp = new int[k, 2]; for (int i = 0; i < k; i++) { for (int j = 0; j < 2; j++) { dp[i, j] = 0; } } // Traverse the matrix v[][] for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check if i+j is odd or even if ((i + j) % 2 == 0) // Increment the value // dp[v[i][j]-1][0] by 1 dp[v[i][j] - 1, 0]++; else // Increment the value // dp[v[i][j]-1][1] by 1 dp[v[i][j] - 1, 1]++; } } // Iterate in range[0, k-1] using i for (int i = 0; i < k; i++) { // Iterate in range[i+1, k-1] using j for (int j = i + 1; j < k; j++) { // Update the ans ans += dp[i, 0] * dp[j, 1]; ans += dp[i, 1] * dp[j, 0]; } } // Print the answer Console.Write(ans); } // Driver code static void Main() { List<List<int> > mat = new List<List<int>>(); mat.Add(new List<int>(new int[]{1, 2})); mat.Add(new List<int>(new int[]{3, 4})); int K = 4; numberofpairs(mat, K); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach // Function to count ways to remove pairs // such that the remaining elements can // be arranged in pairs // vertically or horizontally function numberofpairs(v, k) { // Store the size of matrix let n = v.length; // If N is odd, then no // such pair exists if (n % 2 == 1) { document.write(0); return; } // Store the number of // required pairs let ans = 0; // Initialize an auxiliary // matrix and fill it with 0s let dp = new Array(k); for (let i = 0; i < k; i++) { dp[i] = new Array(2); for (let j = 0; j < 2; j++) { dp[i][j] = 0; } } // Traverse the matrix v[][] for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // Check if i+j is odd or even if ((i + j) % 2 == 0) // Increment the value // dp[v[i][j]-1][0] by 1 dp[v[i][j] - 1][0]++; else // Increment the value // dp[v[i][j]-1][1] by 1 dp[v[i][j] - 1][1]++; } } // Iterate in range[0, k-1] using i for (let i = 0; i < k; i++) { // Iterate in range[i+1, k-1] using j for (let j = i + 1; j < k; j++) { // Update the ans ans += dp[i][0] * dp[j][1]; ans += dp[i][1] * dp[j][0]; } } // Print the answer document.write(ans + "</br>"); } let mat = [ [ 1, 2 ], [ 3, 4 ] ]; let K = 4; numberofpairs(mat, K); </script> |
Output:
4
Time Complexity: O(N2 + K2)
Auxiliary Space: O(K)
Share your thoughts in the comments
