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 ith row and jth 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 ith row and jth 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 ith row and jth 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 ith row and jth 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 conditionsvoid 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 Codeint 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 approachimport java.io.*;class GFG{// Function to find the matrix, A[][]// satisfying the given conditionsstatic 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 Codepublic 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 conditionsdef 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 CodeB = [[ 1, 1, 1 ], [ 1, 1, 1 ]]N = len(B)M = len(B[0])# Function CallfindOriginalMatrix(B, N, M)# This code is contributed by splevel62 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the matrix, A[][]// satisfying the given conditionsstatic 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 Codestatic 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*M2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
