Given four integers N, M, A, B where N is the number of rows and M is the number of columns, the task is to check if is possible to create a binary matrix of dimensions N x M such that every row has A number of 1s and every column has a B number of 1s. If any such matrix is possible then print it else print “-1”.
Examples:
Input: N = 3, M = 6, A = 2, B = 1
Output:
1 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 1
Explanation:
Every row has A ones i.e. 2 and every column has B ones i.e., 1.Input: N = 2, M = 2, A = 2, B = 1
Output: No
Explanation:
It is not possible to create such a 2 x 2 matrix in which every row has 2 ones and every column has 1 ones because of the following two observations:
1. For every row place two ones because of which we will never be able to have one 1 in every column.
1 1
1 12. For every column place one 1 because of which we can never have 2 ones in every row.
1 0
0 1
Approach: The idea is to observe that since each row should have exactly A 1s, and each column should have exactly B 1s, hence the number of ones in all rows A * N should be equal to the number of 1s in all columns B * M. Thus, the desired matrix exists if and only if A*N = B*M. Below is the illustration:
- Find any number 0 < d < M such that (d * N)%M == 0, where A % B is the remainder of dividing A by B.
- In the first row of the desired matrix, insert the ones at the positions [1, A].
- In the ith row, put the ones, as in the i – 1 row, but cyclically shifted by d to the right.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Number of rowsconst int n = 3;// Number of columnsconst int m = 6;// Function that prints the matrix// if it existsvoid printMatrix(int arr[][m], string ans){ if (ans == "No") cout << "No\n"; else { // Print if matrix exists for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << arr[i][j] << " "; cout << '\n'; } }}// Function to check if it is possible// to create a matrix such that every// row has A 1s & every column has B 1svoid createMatrix(int a, int b){ int matrix[n][m], row[n], col[m]; // Initialize all matrix // entries equal to 0 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { matrix[i][j] = 0; } } // Initialize the number of // ones required in every row for (int i = 0; i < n; i++) row[i] = a; // Initialize the number of // ones required in each column for (int i = 0; i < m; i++) col[i] = b; int l = 0, d = 0; // Check if the total number of // ones required in every row is // not equal to total number of // ones required in every column // then print No if (n * a != m * b) printMatrix(matrix, "No"); else { for (int i = 0; i < n; i++) { int j; if (l == m) l = 0; for (j = l; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is a // place to be filled matrix[i][j] = 1; // Decrease the number of // ones required in ith row row[i]--; // Decrease the number of // ones required in jth column col[j]--; d = j; } } l = d + 1; if (row[i] != 0) { for (j = 0; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is // a place to be filled matrix[i][j] = 1; // Decrease the number of 1s // required in ith row row[i]--; // Decrease the number of 1s // required in jth column col[j]--; l = j + 1; } // Break the loop if no place // is left for ones to filled if (row[i] == 0) break; } } } // Function call to print the matrix printMatrix(matrix, "Yes"); }}// Driver Codeint main(){ // Number of ones required // in every row int a = 2; // Number of ones required // in every column int b = 1; // Function call createMatrix(a, b); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Number of rowsstatic int n = 3;// Number of columnsstatic int m = 6;// Function that prints the matrix// if it existsstatic void printMatrix(int arr[][], String ans){ if (ans == "No") System.out.print("No\n"); else { // Print if matrix exists for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) System.out.print(arr[i][j] + " "); System.out.println(); } }}// Function to check if it is possible// to create a matrix such that every// row has A 1s & every column has B 1sstatic void createMatrix(int a, int b){ int [][]matrix = new int[n][m]; int []row = new int[n]; int []col = new int[m]; // Initialize all matrix // entries equal to 0 for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { matrix[i][j] = 0; } } // Initialize the number of // ones required in every row for(int i = 0; i < n; i++) row[i] = a; // Initialize the number of // ones required in each column for(int i = 0; i < m; i++) col[i] = b; int l = 0, d = 0; // Check if the total number of // ones required in every row is // not equal to total number of // ones required in every column // then print No if (n * a != m * b) printMatrix(matrix, "No"); else { for(int i = 0; i < n; i++) { int j; if (l == m) l = 0; for(j = l; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is a // place to be filled matrix[i][j] = 1; // Decrease the number of // ones required in ith row row[i]--; // Decrease the number of // ones required in jth column col[j]--; d = j; } } l = d + 1; if (row[i] != 0) { for(j = 0; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is // a place to be filled matrix[i][j] = 1; // Decrease the number of 1s // required in ith row row[i]--; // Decrease the number of 1s // required in jth column col[j]--; l = j + 1; } // Break the loop if no place // is left for ones to filled if (row[i] == 0) break; } } } // Function call to print the matrix printMatrix(matrix, "Yes"); }}// Driver Codepublic static void main(String[] args){ // Number of ones required // in every row int a = 2; // Number of ones required // in every column int b = 1; // Function call createMatrix(a, b);}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above approach# Number of rowsn = 3# Number of columnsm = 6# Function that prints the matrix# if it existsdef printMatrix(arr, ans): if (ans == "No"): print("No") else: # Print if matrix exists for i in range(n): for j in range(m): print(arr[i][j], end = " ") print()# Function to check if it is possible# to create a matrix such that every# row has A 1s & every column has B 1sdef createMatrix(a, b): matrix = [[0 for i in range(m)] for i in range(n)] row = [a for i in range(n)] col = [b for i in range(m)] l = 0 d = 0 # Check if the total number of # ones required in every row is # not equal to total number of # ones required in every column # then print No if (n * a != m * b): printMatrix(matrix, "No") else: for i in range(n): j = 0 if (l == m): l = 0 for j in range(l, m): if (row[i] > 0 and col[j] > 0): # Fill a one if there is a # place to be filled matrix[i][j] = 1 # Decrease the number of # ones required in ith row row[i] -= 1 # Decrease the number of # ones required in jth column col[j] -= 1 d = j l = d + 1 if (row[i] != 0): for j in range(m): if (row[i] > 0 and col[j] > 0): # Fill a one if there is # a place to be filled matrix[i][j] = 1 # Decrease the number of 1s # required in ith row row[i] -= 1 # Decrease the number of 1s # required in jth column col[j] -= 1 l = j + 1 # Break the loop if no place # is left for ones to filled if (row[i] == 0): break # Function call to print matrix printMatrix(matrix, "Yes")# Driver Codeif __name__ == '__main__': # Number of ones required # in every row a = 2 # Number of ones required # in every column b = 1 # Function call createMatrix(a, b)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Number of rowsstatic int n = 3;// Number of columnsstatic int m = 6;// Function that prints the matrix// if it existsstatic void printMatrix(int [,]arr, String ans){ if (ans == "No") Console.Write("No\n"); else { // Print if matrix exists for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) Console.Write(arr[i, j] + " "); Console.WriteLine(); } }}// Function to check if it is possible// to create a matrix such that every// row has A 1s & every column has B 1sstatic void createMatrix(int a, int b){ int [,]matrix = new int[n, m]; int []row = new int[n]; int []col = new int[m]; // Initialize all matrix // entries equal to 0 for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { matrix[i, j] = 0; } } // Initialize the number of // ones required in every row for(int i = 0; i < n; i++) row[i] = a; // Initialize the number of // ones required in each column for(int i = 0; i < m; i++) col[i] = b; int l = 0, d = 0; // Check if the total number of // ones required in every row is // not equal to total number of // ones required in every column // then print No if (n * a != m * b) printMatrix(matrix, "No"); else { for(int i = 0; i < n; i++) { int j; if (l == m) l = 0; for(j = l; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is a // place to be filled matrix[i,j] = 1; // Decrease the number of // ones required in ith row row[i]--; // Decrease the number of // ones required in jth column col[j]--; d = j; } } l = d + 1; if (row[i] != 0) { for(j = 0; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is // a place to be filled matrix[i,j] = 1; // Decrease the number of 1s // required in ith row row[i]--; // Decrease the number of 1s // required in jth column col[j]--; l = j + 1; } // Break the loop if no place // is left for ones to filled if (row[i] == 0) break; } } } // Function call to print the matrix printMatrix(matrix, "Yes"); }}// Driver Codepublic static void Main(String[] args){ // Number of ones required // in every row int a = 2; // Number of ones required // in every column int b = 1; // Function call createMatrix(a, b);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// JavaScript program for the above approach // Number of rowslet n = 3; // Number of columnslet m = 6; // Function that prints the matrix// if it existsfunction printMatrix(arr, ans){ if (ans == "No") document.write("No\n"); else { // Print if matrix exists for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) document.write(arr[i][j] + " "); document.write("<br/>"); } }} // Function to check if it is possible// to create a matrix such that every// row has A 1s & every column has B 1sfunction createMatrix(a, b){ let matrix = new Array(n); // Loop to create 2D array using 1D array for (var i = 0; i < matrix.length; i++) { matrix[i] = new Array(2); } let row = Array.from({length: n}, (_, i) => 0); let col = Array.from({length: m}, (_, i) => 0); // Initialize all matrix // entries equal to 0 for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) { matrix[i][j] = 0; } } // Initialize the number of // ones required in every row for(let i = 0; i < n; i++) row[i] = a; // Initialize the number of // ones required in each column for(let i = 0; i < m; i++) col[i] = b; let l = 0, d = 0; // Check if the total number of // ones required in every row is // not equal to total number of // ones required in every column // then print No if (n * a != m * b) printMatrix(matrix, "No"); else { for(let i = 0; i < n; i++) { let j; if (l == m) l = 0; for(j = l; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is a // place to be filled matrix[i][j] = 1; // Decrease the number of // ones required in ith row row[i]--; // Decrease the number of // ones required in jth column col[j]--; d = j; } } l = d + 1; if (row[i] != 0) { for(j = 0; j < m; j++) { if (row[i] > 0 && col[j] > 0) { // Fill a one if there is // a place to be filled matrix[i][j] = 1; // Decrease the number of 1s // required in ith row row[i]--; // Decrease the number of 1s // required in jth column col[j]--; l = j + 1; } // Break the loop if no place // is left for ones to filled if (row[i] == 0) break; } } } // Function call to print the matrix printMatrix(matrix, "Yes"); }} // Driver Code // Number of ones required // in every row let a = 2; // Number of ones required // in every column let b = 1; // Function call createMatrix(a, b); </script> |
Output:
1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
Time Complexity: O(N*M), as we are using nested loops to traverse N*M times.
Auxiliary Space: O(N*M), as we are using extra space for matrix.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
