Given two integers N and M, the task is to find the numbers of ways to form a matrix of size N * M consisting only of 1 or -1, such that the product of integers in each row and each column is equal to 1 or -1.
Examples:
Input: N = 2, M = 2
Output: 4
Explanation: Possible ways to get product of each row and column as 1 are,
{{1, 1}, {1, 1}} and {{-1, -1}, {-1, -1}}
Possible ways to get product of each row and column as -1 are, {{1, -1}, {-1, 1}} and {{-1, 1}, {1, -1}} Hence, number of ways = 2 + 2 = 4Input: N = 3, M = 3
Output: 32
Explanation: There are 16 ways to get product as 1 and 16 ways to get product as -1. Hence, number of ways = 16 + 16 = 32
Naive Approach:
The simplest approach to solve this problem is to generate all possible matrices of size N * M and for each of them, calculate the product of all rows and columns and check if it is 1 or -1.
Time complexity: O(2N*M)
Auxiliary Space: O(M*N)
Efficient Approach: Assume, first N-1 rows and first M-1 columns are filled by 1 or -1. Now, the product of each row up to N-1 rows and each column up to M-1 columns would either be 1 or -1. There are a total 2 (N-1) * (M-1) Ways to form a matrix of size (N-1)*(M-1) filled with 1 or -1. Depending on what is needed as a product of N rows and M columns, the last row and column can be filled accordingly.
Follow the steps to solve the problem:
- If N + M is even,
Number of possible matrices to get the product as 1 = 2 (N-1) * (M-1)
Number of possible matrices to get product as -1 = 2 (N-1) * (M-1) - If N + M is odd,
Number of possible matrices to get the product as 1 = 2 (N-1) * (M-1)
Number of possible matrices to get the product as -1 = 0
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include<bits/stdc++.h>using namespace std;// Function to return the// number of possible waysvoid Solve(int N, int M){ int temp = (N - 1) * (M - 1); int ans = pow(2, temp); // Check if product can be -1 if ((N + M) % 2 != 0) cout << ans; else cout << 2 * ans; cout << endl;}// Driver Codeint main(){ int N = 3; int M = 3; Solve(N, M); return 0;} |
Java
// Java implementation of the above approach import java.util.Arrays;class GFG{ // Function to return the// number of possible waysstatic void Solve(int N, int M){ int temp = (N - 1) * (M - 1); int ans = (int)(Math.pow(2, temp)); // Check if product can be -1 if ((N + M) % 2 != 0) System.out.print(ans); else System.out.print(2 * ans);}// Driver code public static void main (String[] args) { int N = 3; int M = 3; Solve(N, M);} } // This code is contributed by Shubham Prakash |
Python3
# Python3 program to implement# the above approach# Function to return# possible number of waysdef Solve(N, M): temp = (N - 1) * (M - 1) ans = pow(2, temp) # Check if product can be -1 if ((N + M) % 2 != 0): print(ans) else: print(2 * ans) # driver codeif __name__ == '__main__': N, M = 3, 3 Solve(N, M)# This code is contributed by Sri_srajit |
C#
// C# implementation of the above approach using System;class GFG{ // Function to return the// number of possible waysstatic void Solve(int N, int M){ int temp = (N - 1) * (M - 1); int ans = (int)(Math.Pow(2, temp)); // Check if product can be -1 if ((N + M) % 2 != 0) Console.Write(ans); else Console.Write(2 * ans);}// Driver Codepublic static void Main(string[] args){ int N = 3; int M = 3; Solve(N, M);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program implementation// of the approach// Function to return the// number of possible waysfunction Solve(N, M){ let temp = (N - 1) * (M - 1); let ans = (Math.pow(2, temp)); // Check if product can be -1 if ((N + M) % 2 != 0) document.write(ans); else document.write(2 * ans);}// Driver Code let N = 3; let M = 3; Solve(N, M); </script> |
C
// C implementation of// the above approach#include<stdio.h>#include<math.h>// Function to return the// number of possible waysvoid Solve(int N, int M){ int temp = (N - 1) * (M - 1); int ans = pow(2, temp); // Check if product can be -1 if ((N + M) % 2 != 0) printf("%d",ans); else printf("%d",(2*ans)); printf("\n");}// Driver Codevoid main(){ int N = 3; int M = 3; Solve(N, M);} |
32
Time complexity: O(log(N*M))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
