Dado un número entero N que es un múltiplo de 4 , la tarea es encontrar una cuadrícula N x N para la cual el xor bit a bit de cada fila y columna sea el mismo.
Ejemplos:
Entrada: N = 4
Salida:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Entrada: N = 8
Salida:
0 1 2 3 16 17 18 19
4 5 6 7 20 21 22 23
8 9 10 11 24 25 26 27
12 13 14 15 28 29 30 31
32 33 34 35 48 49 50 51
36 37 38 39 52 53 54 55
40 41 42 43 56 57 58 59
44 45 46 47 62 6 3
Enfoque: para resolver este problema, fijemos el xor de cada fila y columna en 0, ya que el xor de 4 números consecutivos a partir de 0 es 0. Aquí hay un ejemplo de una array de 4 x 4:
0 ^ 1 ^ 2 ^ 3 = 0
4 ^ 5 ^ 6 ^ 7 = 0
8 ^ 9 ^ 10 ^ 11 = 0
12 ^ 13 ^ 14 ^ 15 = 0
y así sucesivamente.
Si observa en el ejemplo anterior, el xor de cada fila y columna es 0. Ahora necesitamos colocar los números de tal manera que el xor de cada fila y columna sea 0. Entonces podemos dividir nuestra array N x N en arrays más pequeñas de 4 x 4 con N / 4 filas y columnas y llene las celdas de manera que el xor de cada fila y columna sea 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the n x n matrix
// that satisfies the given condition
void findGrid(int n)
{
int arr[n][n];
// Initialize x to 0
int x = 0;
// Divide the n x n matrix into n / 4 matrices
// for each of the n / 4 rows where
// each matrix is of size 4 x 4
for (int i = 0; i < n / 4; i++) {
for (int j = 0; j < n / 4; j++) {
for (int k = 0; k < 4; k++) {
for (int l = 0; l < 4; l++) {
arr[i * 4 + k][j * 4 + l] = x;
x++;
}
}
}
}
// Print the generated matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << arr[i][j] << " ";
}
cout << "\n";
}
}
// Driver code
int main()
{
int n = 4;
findGrid(n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
// Function to find the n x n matrix
// that satisfies the given condition
static void findGrid(int n)
{
int [][]arr = new int[n][n];
// Initialize x to 0
int x = 0;
// Divide the n x n matrix into n / 4 matrices
// for each of the n / 4 rows where
// each matrix is of size 4 x 4
for (int i = 0; i < n / 4; i++)
{
for (int j = 0; j < n / 4; j++)
{
for (int k = 0; k < 4; k++)
{
for (int l = 0; l < 4; l++)
{
arr[i * 4 + k][j * 4 + l] = x;
x++;
}
}
}
}
// Print the generated matrix
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
System.out.print(arr[i][j] + " ");
}
System.out.println(" ");
}
}
// Driver code
public static void main (String[] args)
{
int n = 4;
findGrid(n);
}
}
// This code is contributed by ajit.
Python3
# Python3 implementation of the approach # Function to find the n x n matrix # that satisfies the given condition def findGrid(n): arr = [[0 for k in range(n)] for l in range(n)] # Initialize x to 0 x = 0 # Divide the n x n matrix into n / 4 matrices # for each of the n / 4 rows where # each matrix is of size 4 x 4 for i in range(n // 4): for j in range(n // 4): for k in range(4): for l in range(4): arr[i * 4 + k][j * 4 + l] = x x += 1 # Print the generated matrix for i in range(n): for j in range(n): print(arr[i][j], end = " ") print() # Driver code n = 4 findGrid(n) # This code is contributed by divyamohan123
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to find the n x n matrix
// that satisfies the given condition
static void findGrid(int n)
{
int [,]arr = new int[n, n];
// Initialize x to 0
int x = 0;
// Divide the n x n matrix into n / 4 matrices
// for each of the n / 4 rows where
// each matrix is of size 4 x 4
for (int i = 0; i < n / 4; i++)
{
for (int j = 0; j < n / 4; j++)
{
for (int k = 0; k < 4; k++)
{
for (int l = 0; l < 4; l++)
{
arr[i * 4 + k, j * 4 + l] = x;
x++;
}
}
}
}
// Print the generated matrix
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(arr[i, j] + " ");
}
Console.WriteLine(" ");
}
}
// Driver code
public static void Main (String[] args)
{
int n = 4;
findGrid(n);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the approach
// Function to find the n x n matrix
// that satisfies the given condition
function findGrid(n)
{
let arr = new Array(n);
for (let i = 0; i < n; i++)
arr[i] = new Array(n);
// Initialize x to 0
let x = 0;
// Divide the n x n matrix into n / 4 matrices
// for each of the n / 4 rows where
// each matrix is of size 4 x 4
for (let i = 0; i < parseInt(n / 4); i++) {
for (let j = 0; j < parseInt(n / 4); j++) {
for (let k = 0; k < 4; k++) {
for (let l = 0; l < 4; l++) {
arr[i * 4 + k][j * 4 + l] = x;
x++;
}
}
}
}
// Print the generated matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
document.write(arr[i][j] + " ");
}
document.write("<br>");
}
}
// Driver code
let n = 4;
findGrid(n);
</script>
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por syntaxerror y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA