Dado un número entero N. La tarea es generar una array cuadrada de ( nxn ) que tenga los elementos que van desde 1 hasta n^2 con la siguiente condición:
- Los elementos de la array deben ser distintos, es decir, deben usarse solo una vez.
- Números que van del 1 al n^2
- Cada subarray que elija debe tener la suma de los elementos de las esquinas opuestas como pares, es decir, la suma de los elementos superior izquierdo e inferior derecho debe ser uniforme y la suma de los elementos superior derecho e inferior izquierdo debe ser uniforme.
Esta propiedad debe aplicarse a todas las subarrays de la array. Necesitas generar una subarray par
Ejemplos:
Entrada: 2
Salida: 1 2
4 3
Explicación: Aquí la suma de 1+3=4 es par y 2+4=6 es parEntrada: 4
Salida: 1 2 3
4 5 6
7 8 9
Explicación: La subarray [1 2 4 5], [2 3 5 6], [4 5 7 8], [5 6 8 9], [1 2 3 4 5 6 7 8 9] satisface la condición de elementos de esquina opuestos
que tienen una suma par
Acercarse:
Como sabemos, para que la suma de dos elementos sea par, puede ser Suma de IMPAR e IMPAR o Suma de PAR y PAR. En cualquiera de los dos casos, para que la suma de los elementos de las esquinas sea par, debemos asegurarnos de que los elementos dispuestos en el patrón diagonal sean pares o impares. Así que hacemos la array 2d que tiene diagonales como todas las probabilidades o todos los pares para encontrar cualquier subarray que tenga elementos de esquina que sumen pares. El siguiente enfoque se puede seguir para el mismo.
- Cuando n es impar, las diagonales ya están en todos los elementos pares o impares, por lo que no necesitamos modificar y generar una array 2d simple
- Cuando n es par, la array generada no satisface la propiedad de tener una suma par de los elementos de las esquinas opuestas de las subarrays, por lo que invertimos los elementos de las filas alternas para que las diagonales de cada subarray sean todas pares o impares.
A continuación se muestra la implementación.
C++
// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
void sub_mat_even(int N)
{
// Counter to initialize
// the values in 2-D array
int K = 1;
// To create a 2-D array
// from to 1 to N*2
int A[N][N];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
A[i][j] = K;
K++;
}
}
// If found even we reverse
// the alternate row elements
// to get all diagonal elements
// as all even or all odd
if(N % 2 == 0)
{
for(int i = 0; i < N; i++)
{
if(i % 2 == 1)
{
int s = 0;
int l = N - 1;
// Reverse the row
while(s < l)
{
swap(A[i][s],
A[i][l]);
s++;
l--;
}
}
}
}
// Print the formed array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
cout << A[i][j] << " ";
}
cout << endl;
}
}
// Driver code
int main()
{
int N = 4;
// Function call
sub_mat_even(N);
}
// This code is contributed by mishrapriyanshu557
Java
// Java program for
// the above approach
import java.io.*;
class GFG{
static void sub_mat_even(int N)
{
// Counter to initialize
// the values in 2-D array
int K = 1;
// To create a 2-D array
// from to 1 to N*2
int[][] A = new int[N][N];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
A[i][j] = K;
K++;
}
}
// If found even we reverse
// the alternate row elements
// to get all diagonal elements
// as all even or all odd
if (N % 2 == 0)
{
for(int i = 0; i < N; i++)
{
if (i % 2 == 1)
{
int s = 0;
int l = N - 1;
// Reverse the row
while (s < l)
{
swap(A[i], s, l);
s++;
l--;
}
}
}
}
// Print the formed array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
System.out.print(A[i][j] + " ");
}
System.out.println();
}
}
private static void swap(int[] A, int s, int l)
{
int temp = A[s];
A[s] = A[l];
A[l] = temp;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
// Function call
sub_mat_even(N);
}
}
// This code is contributed by jithin
Python3
# Python3 program for # the above approach import itertools def sub_mat_even(n): temp = itertools.count(1) # create a 2d array ranging # from 1 to n^2 l = [[next(temp)for i in range(n)]for i in range(n)] # If found even we reverse the alternate # row elements to get all diagonal elements # as all even or all odd if n%2 == 0: for i in range(0,len(l)): if i%2 == 1: l[i][:] = l[i][::-1] # Printing the array formed for i in range(n): for j in range(n): print(l[i][j],end=" ") print() n = 4 sub_mat_even(n)
C#
// C# program for
// the above approach
using System;
class GFG {
static void sub_mat_even(int N)
{
// Counter to initialize
// the values in 2-D array
int K = 1;
// To create a 2-D array
// from to 1 to N*2
int[,] A = new int[N, N];
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
A[i, j] = K;
K++;
}
}
// If found even we reverse
// the alternate row elements
// to get all diagonal elements
// as all even or all odd
if (N % 2 == 0)
{
for(int i = 0; i < N; i++)
{
if (i % 2 == 1)
{
int s = 0;
int l = N - 1;
// Reverse the row
while (s < l)
{
int temp = A[i, s];
A[i, s] = A[i, l];
A[i, l] = temp;
s++;
l--;
}
}
}
}
// Print the formed array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
Console.Write(A[i, j] + " ");
}
Console.WriteLine();
}
}
static void Main() {
int N = 4;
// Function call
sub_mat_even(N);
}
}
// This code is contributed by divyeshrabadiya07
Producción:
1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13
Este enfoque tiene una complejidad de tiempo O(n*2).
Publicación traducida automáticamente
Artículo escrito por dipesh99kumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA