Dada una array B[][] de dimensiones N * M , la tarea es generar una array A[][] de las mismas dimensiones que se pueda formar de manera que para cualquier elemento B[i][j] sea igual a Bitwise OR de todos los elementos en la i -ésima fila y la j -ésima columna de A[][] . Si no existe tal array, imprima » No es posible «. De lo contrario, imprima la array A[][] .
Ejemplos:
Entrada: B[][] = {{1, 1, 1}, {1, 1, 1}}
Salida:
1 1 1
1 1 1
Explicación:
B[0][0] = 1 = OR bit a bit de todos los elementos en la fila 0 y la columna 0 de A[][].
B[0][1] = 1 = OR bit a bit de todos los elementos en la fila 0 y la columna 1 de A[][].
B[0][2] = 1 = O bit a bit de todos los elementos en la fila 0 y la columna 2 de A[][].
B[1][0] = 1 = OR bit a bit de todos los elementos en la fila 1 y la columna 0 de A[][].
B[1][1] = 1 = OR bit a bit de todos los elementos en la 1.ª fila y 1.ª columna de A[][].
B[1][2] = 1 = OR bit a bit de todos los elementos en la 1.ª fila y 2.ª columna de A[][].Entrada: B[][] = {{1, 0, 0}, {0, 0, 0}}
Salida: No es posible
Enfoque: La idea se basa en la observación de que si cualquier elemento B[i][j] = 0 , entonces todos los elementos en la i -ésima fila y la j -ésima columna de la array A[][] serán 0 ya que solo Bitwise OR de combinaciones de 0s da como resultado 0 . Siga los pasos a continuación para resolver el problema:
- Cree una array A[][] de tamaño N*M e inicialice todos sus elementos con 1 .
- Atraviese la array B[][] por filas , usando las variables i y j y si B[i][j] = 0 , luego convierta todos los elementos de la i -ésima fila y la j -ésima columna de la array A[][] como 0 _
- Atraviese la array A[][] en filas , usando las variables i y j y para cada índice (i, j) , encuentre el OR bit a bit de los elementos en la i -ésima fila y la j -ésima columna de la array A[][] y almacenarlo en la variable c . Si c no es igual a B[i][j] , imprima «No posible» y salga del ciclo.
- Después de los pasos anteriores, si no se encuentra la instrucción break, imprima la array generada A[][] .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
1 1 1 1 1 1
Complejidad de Tiempo: O(N*M 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA