Dada una array binaria mat[][] de dimensiones N * N , la tarea es verificar si Bitwise AND de los números decimales obtenidos al concatenar los elementos de las diagonales primarias y secundarias es mayor que Bitwise AND de los números decimales obtenidos por los elementos presentes en la fila y columna del medio. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Nota: concatene los elementos de la array de izquierda a derecha y de arriba a abajo solamente. Si N es par, entonces saque la primera fila/columna del medio de las dos.
Ejemplos:
Entrada: M[][] = {{1, 0, 1}, {0, 0, 1}, {0, 1, 1}}
Salida: No
Explicación:
El número formado al concatenar elementos diagonales principales es “101” .
El número formado por la concatenación de elementos diagonales cruzados es “001”.
El número formado por la concatenación de elementos en la fila central es «001».
El número formado por la concatenación de elementos en la columna central es “001”.
Por lo tanto, el AND bit a bit de “101” y “001” es el mismo que el AND bit a bit de “001” y “001”.Entrada: M[][] = {{0, 1, 1}, {0, 0, 0}, {0, 1, 1}}
Salida: Sí
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array dada y agregar el número correspondiente a una variable, digamos P, si la fila actual es igual a la columna actual, a una variable, digamos S, si la fila es N-columna , a una variable, digamos MR, si la fila es igual a N/2 , y a una variable, digamos MC, si la columna es N/2 . Después de completar los pasos anteriores, si Bitwise AND de P y S es mayor que Bitwise AND de MR y MC , escriba “Sí” . De lo contrario, imprima«No».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to convert obtained binary
// representation to decimal value
int convert(vector<int> p)
{
// Stores the resultant number
int ans = 0;
// Traverse string arr
for(int i : p)
{
ans = (ans << 1) | i;
}
// Return the number formed
return ans;
}
// Function to count the number of
// set bits in the number num
int count(int num)
{
// Stores the count of set bits
int ans = 0;
// Iterate until num > 0
while (num > 0)
{
ans += num & 1;
num >>= 1;
}
return ans;
}
// Function to check if the given matrix
// satisfies the given condition or not
void checkGoodMatrix(vector<vector<int> > mat)
{
vector<int> P;
vector<int> S;
vector<int> MR;
vector<int> MC;
// To get P, S, MR, and MC
for(int i = 0; i < mat.size(); i++)
{
for(int j = 0; j < mat[0].size(); j++)
{
if (i == j)
P.push_back(mat[i][j]);
if (i + j == mat.size() - 1)
S.push_back(mat[i][j]);
if (i == floor((mat.size() - 1) / 2))
MR.push_back(mat[i][j]);
if (j == floor((mat.size() - 1) / 2))
MC.push_back(mat[i][j]);
}
}
reverse(S.begin(), S.end());
// Stores decimal equivalents
// of binary representations
int P0 = convert(P);
int S0 = convert(S);
int MR0 = convert(MR);
int MC0 = convert(MC);
// Gett the number of set bits
int setBitsPS = count((P0 & S0));
int setBitsMM = count((MR0 & MC0));
// Print the answer
if (setBitsPS > setBitsMM)
cout << "Yes";
else
cout << "No";
}
// Driver code
int main()
{
vector<vector<int>> mat = { { 1, 0, 1 },
{ 0, 0, 1 },
{ 0, 1, 1 } };
checkGoodMatrix(mat);
}
// This code is contributed by nirajgusain5
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
class GFG{
// Function to convert obtained binary
// representation to decimal value
static int convert(ArrayList<Integer> p)
{
// Stores the resultant number
int ans = 0;
// Traverse string arr
for(int i: p)
{
ans = (ans << 1) | i;
}
// Return the number formed
return ans;
}
// Function to count the number of
// set bits in the number num
static int count(int num)
{
// Stores the count of set bits
int ans = 0;
// Iterate until num > 0
while (num > 0)
{
ans += num & 1;
num >>= 1;
}
return ans;
}
// Function to check if the given matrix
// satisfies the given condition or not
static void checkGoodMatrix(int mat[][])
{
ArrayList<Integer> P = new ArrayList<Integer>();
ArrayList<Integer> S = new ArrayList<Integer>();
ArrayList<Integer> MR = new ArrayList<Integer>();
ArrayList<Integer> MC = new ArrayList<Integer>();
// To get P, S, MR, and MC
for(int i = 0; i < mat.length; i++)
{
for(int j = 0; j < mat[0].length; j++)
{
if (i == j)
P.add(mat[i][j]);
if (i + j == mat.length - 1)
S.add(mat[i][j]);
if (i == Math.floor((mat.length - 1) / 2))
MR.add(mat[i][j]);
if (j == Math.floor((mat.length - 1) / 2))
MC.add(mat[i][j]);
}
}
Collections.reverse(S);
// Stores decimal equivalents
// of binary representations
int P0 = convert(P);
int S0 = convert(S);
int MR0 = convert(MR);
int MC0 = convert(MC);
// Gett the number of set bits
int setBitsPS = count((P0 & S0));
int setBitsMM = count((MR0 & MC0));
// Print the answer
if (setBitsPS > setBitsMM)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
int mat[][] = { { 1, 0, 1 },
{ 0, 0, 1 },
{ 0, 1, 1 } };
checkGoodMatrix(mat);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach
# Functio to convert obtained binary
# representation to decimal value
def convert(arr):
# Stores the resultant number
ans = 0
# Traverse string arr
for i in arr:
ans = (ans << 1) | i
# Return the number formed
return ans
# Function to count the number of
# set bits in the number num
def count(num):
# Stores the count of set bits
ans = 0
# Iterate until num > 0
while num:
ans += num & 1
num >>= 1
return ans
# Function to check if the given matrix
# satisfies the given condition or not
def checkGoodMatrix(mat):
P = []
S = []
MR = []
MC = []
# To get P, S, MR, and MC
for i in range(len(mat)):
for j in range(len(mat[0])):
if i == j:
P.append(mat[i][j])
if i + j == len(mat)-1:
S.append(mat[i][j])
if i == (len(mat)-1)//2:
MR.append(mat[i][j])
if j == (len(mat)-1)//2:
MC.append(mat[i][j])
S.reverse()
# Stores decimal equivalents
# of binary representations
P = convert(P)
S = convert(S)
MR = convert(MR)
MC = convert(MC)
# Gett the number of set bits
setBitsPS = count(P & S)
setBitsMM = count(MR & MC)
# Print the answer
if setBitsPS > setBitsMM:
print("Yes")
else:
print("No")
# Driver Code
# Given Matrix
mat = [[1, 0, 1], [0, 0, 1], [0, 1, 1]]
checkGoodMatrix(mat)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to convert obtained binary
// representation to decimal value
static int convert(List<int> p)
{
// Stores the resultant number
int ans = 0;
// Traverse string arr
foreach(int i in p)
{
ans = (ans << 1) | i;
}
// Return the number formed
return ans;
}
// Function to count the number of
// set bits in the number num
static int count(int num)
{
// Stores the count of set bits
int ans = 0;
// Iterate until num > 0
while (num > 0)
{
ans += num & 1;
num >>= 1;
}
return ans;
}
// Function to check if the given matrix
// satisfies the given condition or not
static void checkGoodMatrix(int[, ] mat)
{
List<int> P = new List<int>();
List<int> S = new List<int>();
List<int> MR = new List<int>();
List<int> MC = new List<int>();
// To get P, S, MR, and MC
for(int i = 0; i < mat.GetLength(0); i++)
{
for(int j = 0; j < mat.GetLength(1); j++)
{
if (i == j)
P.Add(mat[i, j]);
if (i + j == mat.GetLength(0) - 1)
S.Add(mat[i, j]);
if (i == Math.Floor(
(mat.GetLength(0) - 1) / 2.0))
MR.Add(mat[i, j]);
if (j == Math.Floor(
(mat.GetLength(0) - 1) / 2.0))
MC.Add(mat[i, j]);
}
}
S.Reverse();
// Stores decimal equivalents
// of binary representations
int P0 = convert(P);
int S0 = convert(S);
int MR0 = convert(MR);
int MC0 = convert(MC);
// Gett the number of set bits
int setBitsPS = count((P0 & S0));
int setBitsMM = count((MR0 & MC0));
// Print the answer
if (setBitsPS > setBitsMM)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main(string[] args)
{
int[,] mat = { { 1, 0, 1 },
{ 0, 0, 1 },
{ 0, 1, 1 } };
checkGoodMatrix(mat);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for above approach
// Function to convert obtained binary
// representation to decimal value
function convert(p) {
// Stores the resultant number
let ans = 0;
// Traverse string arr
for (let i of p) {
ans = (ans << 1) | i;
}
// Return the number formed
return ans;
}
// Function to count the number of
// set bits in the number num
function count(num) {
// Stores the count of set bits
let ans = 0;
// Iterate until num > 0
while (num > 0) {
ans += num & 1;
num >>= 1;
}
return ans;
}
// Function to check if the given matrix
// satisfies the given condition or not
function checkGoodMatrix(mat) {
let P = [], S = [], MR = [], MC = [];
// To get P, S, MR, and MC
for (let i = 0; i < mat.length; i++) {
for (let j = 0; j < mat[0].length; j++) {
if (i == j)
P.push(mat[i][j]);
if (i + j == mat.length - 1)
S.push(mat[i][j]);
if (i == Math.floor((mat.length - 1) / 2))
MR.push(mat[i][j]);
if (j == Math.floor((mat.length - 1) / 2))
MC.push(mat[i][j]);
}
}
S.reverse();
// Stores decimal equivalents
// of binary representations
let P0 = convert(P);
let S0 = convert(S);
let MR0 = convert(MR);
let MC0 = convert(MC);
// Gett the number of set bits
let setBitsPS = count((P0 & S0));
let setBitsMM = count((MR0 & MC0));
// Print the answer
if (setBitsPS > setBitsMM)
document.write("Yes");
else
document.write("No");
}
// Driver code
let mat = [[1, 0, 1],
[0, 0, 1],
[0, 1, 1]];
checkGoodMatrix(mat);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
No
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, el enfoque anterior se puede optimizar recorriendo las diagonales , la fila central y la columna central de cada elemento únicamente. Siga los pasos a continuación para resolver el problema:
- Inicialice los vectores auxiliares , digamos P, S, MR y MC para almacenar los elementos conectados de la diagonal principal, la diagonal transversal, la mitad de la fila y la mitad de la columna, respectivamente.
- Iterar sobre el rango [0, N – 1] :
- Agregue el elemento de (i, i) a P , es decir, la diagonal principal.
- Agregue el elemento de (N – 1 – i, i) a S , es decir, cruce la diagonal.
- Agregue el elemento de ((N-1)/2, i) a MR , es decir, en la mitad de la fila.
- Agregue el elemento de ((N-1)/2, i) a MC , es decir, en la mitad de la columna.
- Iterar sobre el rango [0, N – 1] :
- Compruebe si P[i] y S[i] > MR[i] y MC[i], luego imprima “Sí” y regrese.
- De lo contrario, verifique si p[i] & s[i] < MR[i] & MC[i] , luego escriba “No” y regrese.
- Si ninguna de las condiciones anteriores satisface, escriba «No» .
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 check if the matrix
// satisfy the given condition or not
void checkGoodMatrix(
vector<vector<int> > M, int N)
{
// Stores the binary representation
vector<int> p, s, MR, MC;
// Iterate over the range [0, N]
for (int i = 0; i < N; i++) {
// Push element of main diagonal
p.push_back(M[i][i]);
// Push element of cross diagona
s.push_back(M[N - 1 - i][i]);
// Push element of Mid row
MR.push_back(M[(N - 1) / 2][i]);
// Push element of Mid column
MC.push_back(M[i][(N - 1) / 2]);
}
// Check if S & P > MR & MC
for (int i = 0; i < N; i++) {
if (p[i] & s[i] > MR[i] & MC[i]) {
cout << "Yes";
return;
}
else if (p[i] & s[i] < MR[i] & MC[i]) {
cout << "No";
return;
}
}
cout << "No";
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > M{ { 0, 1, 1 },
{ 0, 0, 0 },
{ 0, 1, 1 } };
// Size of the matrix
int N = M.size();
checkGoodMatrix(M, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Vector;
class GFG{
static void checkGoodMatrix(int[][] M, int N)
{
// Stores the binary representation
Vector<Integer> p = new Vector<Integer>();
Vector<Integer> s = new Vector<Integer>();
Vector<Integer> MR = new Vector<Integer>();
Vector<Integer> MC = new Vector<Integer>();
// Iterate over the range [0, N]
for(int i = 0; i < N; i++)
{
// Push element of main diagonal
p.add(M[i][i]);
// Push element of cross diagona
s.add(M[N - 1 - i][i]);
// Push element of Mid row
MR.add(M[(N - 1) / 2][i]);
// Push element of Mid column
MC.add(M[i][(N - 1) / 2]);
}
// Check if S & P > MR & MC
for(int i = 0; i < N; i++)
{
int P = p.get(i);
int S = s.get(i);
int Mr = MR.get(i);
int Mc = MC.get(i);
if ((P & S) > (Mr & Mc))
{
System.out.print("Yes");
return;
}
else if ((P & S) < (Mr & Mc))
{
System.out.print("No");
return;
}
}
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
// Given matrix
int[][] M = { { 0, 1, 1 },
{ 0, 0, 0 },
{ 0, 1, 1 } };
// Size of the matrix
int N = M.length;
checkGoodMatrix(M, N);
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach
# Function to check if the matrix
# satisfy the given condition or not
def checkGoodMatrix(M, N):
# Stores the binary representation
p = []
s = []
MR = []
MC = []
# Iterate over the range [0, N]
for i in range(N):
# Push element of main diagonal
p.append(M[i][i])
# Push element of cross diagona
s.append(M[N - 1 - i][i])
# Push element of Mid row
MR.append(M[(N - 1) // 2][i])
# Push element of Mid column
MC.append(M[i][(N - 1) // 2])
# Check if S & P > MR & MC
for i in range(N):
if (p[i] & s[i] > MR[i] & MC[i]):
print("Yes")
return
elif (p[i] & s[i] < MR[i] & MC[i]):
print("No")
return
print("No")
# Driver Code
# Given matrix
M = [ [ 0, 1, 1 ],
[ 0, 0, 0 ],
[ 0, 1, 1 ] ]
# Size of the matrix
N = len(M)
checkGoodMatrix(M, N)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
static void checkGoodMatrix(int[,] M, int N)
{
// Stores the binary representation
List<int> p = new List<int>();
List<int> s = new List<int>();
List<int> MR = new List<int>();
List<int> MC = new List<int>();
// Iterate over the range [0, N]
for(int i = 0; i < N; i++)
{
// Push element of main diagonal
p.Add(M[i,i]);
// Push element of cross diagona
s.Add(M[N - 1 - i,i]);
// Push element of Mid row
MR.Add(M[(N - 1) / 2,i]);
// Push element of Mid column
MC.Add(M[i,(N - 1) / 2]);
}
// Check if S & P > MR & MC
for(int i = 0; i < N; i++)
{
int P = p[i];
int S = s[i];
int Mr = MR[i];
int Mc = MC[i];
if ((P & S) > (Mr & Mc))
{
Console.WriteLine("Yes");
return;
}
else if ((P & S) < (Mr & Mc))
{
Console.WriteLine("No");
return;
}
}
Console.WriteLine("No");
}
static void Main() {
// Given matrix
int[,] M = { { 0, 1, 1 },
{ 0, 0, 0 },
{ 0, 1, 1 } };
// Size of the matrix
int N = 3;
checkGoodMatrix(M, N);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// JavaScript program for the above approach
function checkGoodMatrix(M, N)
{
// Stores the binary representation
let p = [];
let s = [];
let MR = [];
let MC = [];
// Iterate over the range [0, N]
for(let i = 0; i < N; i++)
{
// Push element of main diagonal
p.push(M[i][i]);
// Push element of cross diagona
s.push(M[N - 1 - i][i]);
// Push element of Mid row
MR.push(M[parseInt((N - 1) / 2, 10)][i]);
// Push element of Mid column
MC.push(M[i][parseInt((N - 1) / 2, 10)]);
}
// Check if S & P > MR & MC
for(let i = 0; i < N; i++)
{
let P = p[i];
let S = s[i];
let Mr = MR[i];
let Mc = MC[i];
if ((P & S) > (Mr & Mc))
{
document.write("Yes");
return;
}
else if ((P & S) < (Mr & Mc))
{
document.write("No");
return;
}
}
document.write("No");
}
// Given matrix
let M = [ [ 0, 1, 1 ],
[ 0, 0, 0 ],
[ 0, 1, 1 ] ];
// Size of the matrix
let N = M.length;
checkGoodMatrix(M, N);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA