Dado un número N , la tarea es construir una array cuadrada de N * N donde la unión de los elementos en alguna i -ésima fila con la i -ésima columna contiene todos los elementos en el rango [1, 2*N-1]. Si no existe tal array, imprima -1.
Nota: Puede haber múltiples soluciones posibles para un N en particular
. Ejemplos:
Entrada: N = 6
Salida:
6 4 2 5 3 1
10 6 5 3 1 2
8 11 6 1 4 3
11 9 7 6 2 4
9 7 10 8 6 5
7 8 9 10 11 6
Explicación:
La array anterior es de 6 * 6 en el que cada i -ésima fila y columna contiene elementos del 1 al 11, como:
1.ª fila y 1.ª columna = {6, 4, 2, 5, 3, 1} & {6, 10, 8, 11, 9 , 7} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
2da fila y 2da columna = {10, 6, 5, 3, 1, 2} & {4, 6, 11, 9, 7, 8} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
3ra fila y 3ra columna = {8, 11, 6, 1, 4 , 3} & {2, 5, 6, 7, 10, 9} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
4ta fila y 4ta columna = {11, 9, 7, 6, 2, 4} & {5, 3, 1, 6, 8, 10} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
5.ª fila y 5.ª columna = {9, 7, 10, 8, 6, 5} y {3, 1, 4, 2, 6, 11} = {1, 2, 3, 4, 5, 6, 7, 8 , 9, 10, 11}
6.ª fila y 6.ª columna = {7, 8, 9, 10, 11, 6} & {1, 2, 3, 4, 5, 6} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
Entrada: N = 6
Salida: -1
Explicación:
No existe tal array posible en la que cada i-ésima fila y i-ésima columna contenga todos los elementos del 1 al 9 Por lo tanto, la respuesta es -1.
Enfoque:
Si observamos detenidamente, podemos ver que:
- Para cualquier número impar excepto 1, la array cuadrada no es posible generar
- Para generar la array cuadrada para orden par, la idea es llenar la mitad superior de los elementos diagonales de la array en el rango de 1 a N-1 y llenar todos los elementos diagonales con la N y la mitad inferior de la diagonal los elementos se pueden completar en número desde el rango N + 1 hasta 2N – 1 .
A continuación se muestra el algoritmo de este enfoque:
- La array de orden impar no se puede llenar como se observa excepto N = 1
- Para Matrix de orden par,
- En primer lugar, rellene todos los elementos diagonales iguales a N.
- Considere las dos mitades de la array divididas en diagonal, cada mitad se puede llenar con N-1 elementos.
- Rellene la mitad superior con elementos de [1, N-1] y la mitad inferior con elementos de [N+1, 2N-1] .
- Como se puede observar fácilmente, existe un patrón en el que el último elemento de la segunda fila siempre puede ser 2.
- Ahora, los elementos consecutivos en la última columna tienen una diferencia de 2. Por lo tanto, la forma generalizada se puede dar como A[i]=[(N-2)+2i]%(N-1)+1 , para todo i desde 1 a N-1
- Simplemente agregue N a todos los elementos de la mitad inferior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
int matrix[100][100];
// Function to find the square matrix
void printRequiredMatrix(int n)
{
// For Matrix of order 1,
// it will contain only 1
if (n == 1) {
cout << "1"
<< "\n";
}
// For Matrix of odd order,
// it is not possible
else if (n % 2 != 0) {
cout << "-1"
<< "\n";
}
// For Matrix of even order
else {
// All diagonal elements of the
// matrix can be N itself.
for (int i = 0; i < n; i++) {
matrix[i][i] = n;
}
int u = n - 1;
// Assign values at desired
// place in the matrix
for (int i = 0; i < n - 1; i++) {
matrix[i][u] = i + 1;
for (int j = 1; j < n / 2; j++) {
int a = (i + j) % (n - 1);
int b = (i - j + n - 1) % (n - 1);
if (a < b)
swap(a, b);
matrix[b][a] = i + 1;
}
}
// Loop to add N in the lower half
// of the matrix such that it contains
// elements from 1 to 2*N - 1
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
matrix[i][j] = matrix[j][i] + n;
// Loop to print the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << matrix[i][j] << " ";
cout << "\n";
}
}
cout << "\n";
}
// Driver Code
int main()
{
int n = 1;
printRequiredMatrix(n);
n = 3;
printRequiredMatrix(n);
n = 6;
printRequiredMatrix(n);
return 0;
}
Java
// Java implementation of the above approach
class GFG {
static int matrix[][] = new int[100][100];
// Function to find the square matrix
static void printRequiredMatrix(int n)
{
// For Matrix of order 1,
// it will contain only 1
if (n == 1) {
System.out.println("1");
}
// For Matrix of odd order,
// it is not possible
else if (n % 2 != 0) {
System.out.println("-1");
}
// For Matrix of even order
else {
// All diagonal elements of the
// matrix can be N itself.
for (int i = 0; i < n; i++) {
matrix[i][i] = n;
}
int u = n - 1;
// Assign values at desired
// place in the matrix
for (int i = 0; i < n - 1; i++) {
matrix[i][u] = i + 1;
for (int j = 1; j < n / 2; j++) {
int a = (i + j) % (n - 1);
int b = (i - j + n - 1) % (n - 1);
if (a < b) {
int temp = a;
a = b;
b = temp;
}
matrix[b][a] = i + 1;
}
}
// Loop to add N in the lower half
// of the matrix such that it contains
// elements from 1 to 2*N - 1
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
matrix[i][j] = matrix[j][i] + n;
// Loop to print the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
System.out.print(matrix[i][j] + " ");
System.out.println() ;
}
}
System.out.println();
}
// Driver Code
public static void main (String[] args)
{
int n = 1;
printRequiredMatrix(n);
n = 3;
printRequiredMatrix(n);
n = 6;
printRequiredMatrix(n);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the above approach
import numpy as np;
matrix = np.zeros((100,100));
# Function to find the square matrix
def printRequiredMatrix(n) :
# For Matrix of order 1,
# it will contain only 1
if (n == 1) :
print("1");
# For Matrix of odd order,
# it is not possible
elif (n % 2 != 0) :
print("-1");
# For Matrix of even order
else :
# All diagonal elements of the
# matrix can be N itself.
for i in range(n) :
matrix[i][i] = n;
u = n - 1;
# Assign values at desired
# place in the matrix
for i in range(n - 1) :
matrix[i][u] = i + 1;
for j in range(1, n//2) :
a = (i + j) % (n - 1);
b = (i - j + n - 1) % (n - 1);
if (a < b) :
a,b = b,a
matrix[b][a] = i + 1;
# Loop to add N in the lower half
# of the matrix such that it contains
# elements from 1 to 2*N - 1
for i in range(n) :
for j in range(i) :
matrix[i][j] = matrix[j][i] + n;
# Loop to print the matrix
for i in range(n) :
for j in range(n) :
print(matrix[i][j] ,end=" ");
print();
print()
# Driver Code
if __name__ == "__main__" :
n = 1;
printRequiredMatrix(n);
n = 3;
printRequiredMatrix(n);
n = 6;
printRequiredMatrix(n);
# This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
class GFG {
static int [,]matrix = new int[100, 100];
// Function to find the square matrix
static void printRequiredMatrix(int n)
{
// For Matrix of order 1,
// it will contain only 1
if (n == 1) {
Console.WriteLine("1");
}
// For Matrix of odd order,
// it is not possible
else if (n % 2 != 0) {
Console.WriteLine("-1");
}
// For Matrix of even order
else
{
// All diagonal elements of the
// matrix can be N itself.
for (int i = 0; i < n; i++) {
matrix[i, i] = n;
}
int u = n - 1;
// Assign values at desired
// place in the matrix
for (int i = 0; i < n - 1; i++) {
matrix[i, u] = i + 1;
for (int j = 1; j < n / 2; j++) {
int a = (i + j) % (n - 1);
int b = (i - j + n - 1) % (n - 1);
if (a < b) {
int temp = a;
a = b;
b = temp;
}
matrix[b, a] = i + 1;
}
}
// Loop to add N in the lower half
// of the matrix such that it contains
// elements from 1 to 2*N - 1
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
matrix[i, j] = matrix[j, i] + n;
// Loop to print the matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
Console.Write(matrix[i, j] + " ");
Console.WriteLine() ;
}
}
Console.WriteLine();
}
// Driver Code
public static void Main (String[] args)
{
int n = 1;
printRequiredMatrix(n);
n = 3;
printRequiredMatrix(n);
n = 6;
printRequiredMatrix(n);
}
}
// This code is contributed by Yash_R
Javascript
<script>
// Javascript implementation of the above approach
let matrix = new Array();
for(let i = 0; i < 100; i++){
let temp = new Array();
for(let j = 0; j < 100; j++){
temp.push([])
}
matrix.push(temp)
}
// Function to find the square matrix
function printRequiredMatrix(n)
{
// For Matrix of order 1,
// it will contain only 1
if (n == 1) {
document.write("1" + "<br>");
}
// For Matrix of odd order,
// it is not possible
else if (n % 2 != 0) {
document.write("-1" + "<br>");
}
// For Matrix of even order
else {
// All diagonal elements of the
// matrix can be N itself.
for (let i = 0; i < n; i++) {
matrix[i][i] = n;
}
let u = n - 1;
// Assign values at desired
// place in the matrix
for (let i = 0; i < n - 1; i++) {
matrix[i][u] = i + 1;
for (let j = 1; j < n / 2; j++) {
let a = (i + j) % (n - 1);
let b = (i - j + n - 1) % (n - 1);
if (a < b){
let temp = a;
a = b;
b = temp
}
matrix[b][a] = i + 1;
}
}
// Loop to add N in the lower half
// of the matrix such that it contains
// elements from 1 to 2*N - 1
for (let i = 0; i < n; i++)
for (let j = 0; j < i; j++)
matrix[i][j] = matrix[j][i] + n;
// Loop to print the matrix
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++)
document.write(matrix[i][j] + " ");
document.write("<br>");
}
}
document.write("<br>");
}
// Driver Code
let n = 1;
printRequiredMatrix(n);
n = 3;
printRequiredMatrix(n);
n = 6;
printRequiredMatrix(n);
// This code is contributed by gfgking
</script>
Producción:
1 -1 6 4 2 5 3 1 10 6 5 3 1 2 8 11 6 1 4 3 11 9 7 6 2 4 9 7 10 8 6 5 7 8 9 10 11 6
Análisis de rendimiento:
- Complejidad del tiempo: como en el enfoque anterior, hay dos bucles para iterar sobre toda la array N*N que toma el tiempo O(N 2 ) en el peor de los casos, por lo tanto, la complejidad del tiempo será O(N 2 ) .
- Complejidad del espacio auxiliar: como en el enfoque anterior, no se usa espacio adicional, por lo tanto, la complejidad del espacio auxiliar será O (1)