Generate a Matrix such that given Matrix elements are equal to Bitwise OR of all corresponding row and column elements of generated Matrix

0 0 9 minutes read

Given a matrix B[][] of dimensions N * M, the task is to generate a matrix A[][] of same dimensions that can be formed such that for any element B[i][j] is equal to Bitwise OR of all elements in the i^th row and j^th column of A[][]. If no such matrix exists, print “Not Possible“. Otherwise, print the matrix A[][].

Examples:

Input: B[][] = {{1, 1, 1}, {1, 1, 1}}
Output:
1 1 1
1 1 1
Explanation:
B[0][0] = 1 = bitwise OR of all elements in 0th row and 0th column of A[][].
B[0][1] = 1 = bitwise OR of all elements in 0th row and 1th column of A[][].
B[0][2] = 1 = bitwise OR of all elements in 0th row and 2nd column of A[][].
B[1][0] = 1 = bitwise OR of all elements in 1th row and 0th column of A[][].
B[1][1] = 1 = bitwise OR of all elements in 1th row and 1th column of A[][].
B[1][2] = 1 = bitwise OR of all elements in 1th row and 2nd column of A[][].

Input: B[][] = {{1, 0, 0}, {0, 0, 0}}
Output: Not Possible

Approach: The idea is based on the observation that if any element B[i][j] = 0, then all the elements in the i^th row and j^th column of matrix A[][] will be 0 since only the Bitwise OR of combinations of 0s results in 0. Follow the steps below to solve the problem:

Create a matrix A[][] of size N*M and initialize all its elements with 1.
Traverse the matrix B[][] row-wise, using variables i and j and if B[i][j] = 0, then make all the elements of i^th row and j^th column of matrix A[][] as 0.
Traverse the matrix A[][] row-wise, using variables i and j and for every index (i, j), find the bitwise OR of the elements in the i^th row and j^th column of matrix A[][] and store it in variable c. If c is not equal to B[i][j], print “Not Possible” and break out of the loop.
After the above steps, if the break statement is not encountered then print the generated matrix A[][].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the matrix, A[][]
// satisfying the given conditions
void findOriginalMatrix(
    vector<vector<int> > B, int N, int M)
{
    // Store the final matrix
    int A[N][M];
 
    // Initialize all the elements of
    // the matrix A with 1
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            A[i][j] = 1;
        }
    }
 
    // Traverse the matrix B[][] row-wise
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
 
            // If B[i][j] is equal to 0
            if (B[i][j] == 0) {
 
                // Mark all the elements of
                // ith row of A[][] as 0
                for (int k = 0; k < M; ++k) {
                    A[i][k] = 0;
                }
 
                // Mark all the elements of
                // jth column of A[][] as 0
                for (int k = 0; k < N; ++k) {
                    A[k][j] = 0;
                }
            }
        }
    }
 
    // Check if the matrix B[][] can
    // be made using matrix A[][]
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
 
            // Store the bitwise OR of
            // all elements of A[][] in
            // ith row and jth column
            int c = 0;
 
            // Traverse through ith row
            for (int k = 0; k < M; ++k) {
                if (c == 1)
                    break;
                c += A[i][k];
            }
 
            // Traverse through jth column
            for (int k = 0; k < N; ++k) {
                if (c == 1)
                    break;
                c += A[k][j];
            }
 
            // If B[i][j] is not equal to
            // c, print "Not Possible"
            if (c != B[i][j]) {
                cout << "Not Possible";
                return;
            }
        }
    }
 
    // Print the final matrix A[][]
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cout << A[i][j] << " ";
        }
        cout << "\n";
    }
}
 
// Driver Code
int main()
{
    vector<vector<int> > B{ { 1, 1, 1 }, { 1, 1, 1 } };
 
    int N = B.size();
    int M = B[0].size();
 
    // Function Call
    findOriginalMatrix(B, N, M);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to find the matrix, A[][]
// satisfying the given conditions
static void findOriginalMatrix(int[][] B, int N, 
                               int M)
{
     
    // Store the final matrix
    int[][] A = new int[N][M];
 
    // Initialize all the elements of
    // the matrix A with 1
    for(int i = 0; i < N; ++i) 
    {
        for(int j = 0; j < M; ++j) 
        {
            A[i][j] = 1;
        }
    }
 
    // Traverse the matrix B[][] row-wise
    for(int i = 0; i < N; ++i) 
    {
        for(int j = 0; j < M; ++j) 
        {
             
            // If B[i][j] is equal to 0
            if (B[i][j] == 0) 
            {
                 
                // Mark all the elements of
                // ith row of A[][] as 0
                for(int k = 0; k < M; ++k) 
                {
                    A[i][k] = 0;
                }
 
                // Mark all the elements of
                // jth column of A[][] as 0
                for(int k = 0; k < N; ++k)
                {
                    A[k][j] = 0;
                }
            }
        }
    }
 
    // Check if the matrix B[][] can
    // be made using matrix A[][]
    for(int i = 0; i < N; ++i) 
    {
        for(int j = 0; j < M; ++j)
        {
             
            // Store the bitwise OR of
            // all elements of A[][] in
            // ith row and jth column
            int c = 0;
 
            // Traverse through ith row
            for(int k = 0; k < M; ++k)
            {
                if (c == 1)
                    break;
                     
                c += A[i][k];
            }
 
            // Traverse through jth column
            for(int k = 0; k < N; ++k)
            {
                if (c == 1)
                    break;
                     
                c += A[k][j];
            }
 
            // If B[i][j] is not equal to
            // c, print "Not Possible"
            if (c != B[i][j])
            {
                System.out.println("Not Possible");
                return;
            }
        }
    }
 
    // Print the final matrix A[][]
    for(int i = 0; i < N; ++i) 
    {
        for(int j = 0; j < M; ++j) 
        {
            System.out.print(A[i][j] + " ");
        }
        System.out.println();
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int[][] B = new int[][]{ { 1, 1, 1 }, 
                             { 1, 1, 1 } };
 
    int N = B.length;
    int M = B[0].length;
 
    // Function Call
    findOriginalMatrix(B, N, M);
}
}
 
// This code is contributed by Dharanendra L V

Python3

# Python program for the above approach
 
# Function to find the matrix, A[][]
# satisfying the given conditions
def findOriginalMatrix(B, N, M) :
   
    # Store the final matrix
    A = [[0]*M]*N
 
    # Initialize all the elements of
    # the matrix A with 1
    for i in range(N) :
        for j in range(M):
            A[i][j] = 1
         
    # Traverse the matrix B[][] row-wise
    for i in range(N) :
        for j in range(M):
 
            # If B[i][j] is equal to 0
            if (B[i][j] == 0) :
 
                # Mark all the elements of
                # ith row of A[][] as 0
                for k in range(M):
                    A[i][k] = 0
                 
                # Mark all the elements of
                # jth column of A[][] as 0
                for k in range(N):
                    A[k][j] = 0
     
    # Check if the matrix B[][] can
    # be made using matrix A[][]
    for i in range(N) :
        for j in range(M):
 
            # Store the bitwise OR of
            # all elements of A[][] in
            # ith row and jth column
            c = 0
 
            # Traverse through ith row
            for k in range(M):
                if (c == 1) :
                    break
                c += A[i][k]
             
            # Traverse through jth column
            for k in range(N):
                if (c == 1) :
                    break
                c += A[k][j]
             
            # If B[i][j] is not equal to
            # c, pr"Not Possible"
            if (c != B[i][j]) :
                print("Not Possible")
                return
 
    # Print the final matrix A[][]
    for i in range(N) :
        for j in range(M):
            print(A[i][j], end = " ")
         
        print()
     
# Driver Code
B = [[ 1, 1, 1 ], [ 1, 1, 1 ]]
 
N = len(B)
M = len(B[0])
 
# Function Call
findOriginalMatrix(B, N, M)
 
# This code is contributed by splevel62

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the matrix, A[][]
// satisfying the given conditions
static void findOriginalMatrix(int[,] B, int N, 
                               int M)
{
     
    // Store the final matrix
    int[,] A = new int[N, M];
 
    // Initialize all the elements of
    // the matrix A with 1
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
            A[i, j] = 1;
        }
    }
 
    // Traverse the matrix B[][] row-wise
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < M; ++j)
        {
             
            // If B[i][j] is equal to 0
            if (B[i, j] == 0)
            {
                 
                // Mark all the elements of
                // ith row of A[][] as 0
                for(int k = 0; k < M; ++k) 
                {
                    A[i, k] = 0;
                }
 
                // Mark all the elements of
                // jth column of A[][] as 0
                for(int k = 0; k < N; ++k) 
                {
                    A[k, j] = 0;
                }
            }
        }
    }
 
    // Check if the matrix B[][] can
    // be made using matrix A[][]
    for(int i = 0; i < N; ++i) 
    {
        for(int j = 0; j < M; ++j)
        {
             
            // Store the bitwise OR of
            // all elements of A[][] in
            // ith row and jth column
            int c = 0;
 
            // Traverse through ith row
            for(int k = 0; k < M; ++k)
            {
                if (c == 1)
                    break;
                     
                c += A[i, k];
            }
 
            // Traverse through jth column
            for(int k = 0; k < N; ++k) 
            {
                if (c == 1)
                    break;
                     
                c += A[k, j];
            }
 
            // If B[i][j] is not equal to
            // c, print "Not Possible"
            if (c != B[i, j]) 
            {
                Console.WriteLine("Not Possible");
                return;
            }
        }
    }
 
    // Print the final matrix A[][]
    for(int i = 0; i < N; ++i) 
    {
        for(int j = 0; j < M; ++j) 
        {
            Console.Write(A[i, j] + " ");
        }
        Console.WriteLine();
    }
}
 
// Driver Code
static public void Main()
{
    int[,] B = new int[,]{ { 1, 1, 1 }, 
                           { 1, 1, 1 } };
 
    int N = B.GetLength(0);
    int M = B.GetLength(1);
 
    // Function Call
    findOriginalMatrix(B, N, M);
}
}
 
// This code is contributed by Dharanendra L V

Javascript

<script>
 
// Javascript program for the above approach
 
    // Function to find the matrix, A
    // satisfying the given conditions
    function findOriginalMatrix(B , N , M)
    {
 
        // Store the final matrix
        var A = Array(N);
        for(var i = 0;i<N;i++)
        A[i] = Array(M).fill(0);
 
        // Initialize all the elements of
        // the matrix A with 1
        for (i = 0; i < N; ++i) {
            for (j = 0; j < M; ++j) {
                A[i][j] = 1;
            }
        }
 
        // Traverse the matrix B row-wise
        for (i = 0; i < N; ++i) {
            for (j = 0; j < M; ++j) {
 
                // If B[i][j] is equal to 0
                if (B[i][j] == 0) {
 
                    // Mark all the elements of
                    // ith row of A as 0
                    for (k = 0; k < M; ++k) {
                        A[i][k] = 0;
                    }
 
                    // Mark all the elements of
                    // jth column of A as 0
                    for (k = 0; k < N; ++k) {
                        A[k][j] = 0;
                    }
                }
            }
        }
 
        // Check if the matrix B can
        // be made using matrix A
        for (i = 0; i < N; ++i) {
            for (j = 0; j < M; ++j) {
 
                // Store the bitwise OR of
                // all elements of A in
                // ith row and jth column
                var c = 0;
 
                // Traverse through ith row
                for (k = 0; k < M; ++k) {
                    if (c == 1)
                        break;
 
                    c += A[i][k];
                }
 
                // Traverse through jth column
                for (k = 0; k < N; ++k) {
                    if (c == 1)
                        break;
 
                    c += A[k][j];
                }
 
                // If B[i][j] is not equal to
                // c, print "Not Possible"
                if (c != B[i][j]) {
                    document.write("Not Possible");
                    return;
                }
            }
        }
 
        // Print the final matrix A
        for (i = 0; i < N; ++i) {
            for (j = 0; j < M; ++j) {
                document.write(A[i][j] + " ");
            }
            document.write("<br/>");
        }
    }
 
    // Driver Code
     
        var B =[[ 1, 1, 1 ], [ 1, 1, 1 ] ];
 
        var N = B.length;
        var M = B[0].length;
 
        // Function Call
        findOriginalMatrix(B, N, M);
 
// This code contributed by gauravrajput1
 
</script>

Output:

1 1 1 
1 1 1

Time Complexity: O(N*M²)
Auxiliary Space: O(N*M)

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!