Check if it is possible to create a matrix such that every row has A 1s and every column has B 1s

0 0 11 minutes read

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 1

2. 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 i^th 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 rows
const int n = 3;
 
// Number of columns
const int m = 6;
 
// Function that prints the matrix
// if it exists
void 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 1s
void 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 Code
int 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 approach
import java.util.*;
 
class GFG{
 
// Number of rows
static int n = 3;
 
// Number of columns
static int m = 6;
 
// Function that prints the matrix
// if it exists
static 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 1s
static 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 Code
public 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 rows
n = 3
 
# Number of columns
m = 6
 
# Function that prints the matrix
# if it exists
def 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 1s
def 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 Code
if __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 approach
using System;
class GFG{
 
// Number of rows
static int n = 3;
 
// Number of columns
static int m = 6;
 
// Function that prints the matrix
// if it exists
static 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 1s
static 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 Code
public 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 rows
let n = 3;
   
// Number of columns
let m = 6;
   
// Function that prints the matrix
// if it exists
function 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 1s
function 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 zambiatek!