Dados dos enteros M y N , la tarea es generar una array MxN que tenga elementos en el rango [1, MxN] tal que el promedio de cualquier subarreglo de cualquier fila sea un número entero. Si no es posible hacerlo, devuelve -1.
Ejemplos:
Entrada: M = 2, N = 3
Salida:
1 3 5
2 4 6
Explicación: Los subarreglos de la primera fila con tamaño mayor que 1 son {1, 3}, {3, 5}, {1, 3, 5}. Las medias son 2, 4 y 3 respectivamente.
Los subarreglos de la segunda fila con un tamaño mayor que 1 son {2, 4}, {4, 6}, {2, 4, 6}. Las medias son 3, 5 y 4 respectivamente.Entrada: M = 1, N = 3
Salida: -1
Explicación: Todos los arreglos posibles son: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1 }, {3, 1, 2}, {3, 2, 1}.
En todo arreglo hay un subarreglo cuya media es un valor decimal y no un número entero.
Enfoque : La solución al enfoque se basa en la siguiente observación matemática:
- El tamaño del subarreglo debe dividir completamente la suma de los elementos para que la media sea un valor integral.
- Los elementos son números naturales del 1 al M*N .
- La suma de los primeros ‘n’ números impares es igual a n 2 y la suma de los primeros ‘n’ números pares es igual a n(n+1) .
Ahora supongamos que de los primeros n elementos impares descartamos los primeros k elementos impares y consideramos el resto como el subarreglo, entonces:
Números totales = n
Números descartados = k
Números en el subarreglo = n – k
Suma de los primeros n números =n 2
Suma de los primeros k números =k 2
Por lo tanto, la suma del subarreglo = n 2 – k 2
=> media = (n 2 – k 2 )/(n – k)
= (n + k)*(n – k)/(n – k)
= (n + k), que es un número entero ya que tanto n como k son números enteros
De manera similar, suponga que a partir de los primeros n elementos pares, deseche los primeros k elementos pares y considere el resto como el subarreglo, entonces:
Números totales = n
Números descartados = k
Números en el subarreglo = n – k
Suma de los primeros n números =n(n + 1)
Suma de los primeros k números =k(k + 1)
Por lo tanto, suma del subarreglo = n(n + 1) ) – k(k + 1)
=> media = (n(n + 1) – k(k + 1))/(n – k)
= (n 2 + n – k 2 – k)/(nk)
= (n 2 – k 2 )/(n – k) + (nk)/(nk)
= (n + k)*(n – k)/(n – k) + 1
= (n + k) + 1, que es un número entero ya que tanto n como k son números enteros.
Siga los pasos mencionados a continuación para implementar la observación anterior:
- A partir de la observación anterior, organice de tal manera que cada fila tenga todos los números pares o todos los números impares.
- Comprueba si hay números iguales de números pares e impares y el MxN debe ser par.
- Si el número de filas es impar, entonces no es posible un arreglo válido porque los elementos pares e impares no se pueden mantener juntos. Siempre habrá al menos una fila con elementos pares e impares.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
void validArrangement(int M, int N)
{
// If N == 1 then the only
// subarray possible is of length 1
// therefore, the mean will
// always be an integer
if (N == 1) {
for (int i = 1; i <= M; i++)
cout << i << endl;
return;
}
// If M is odd the valid
// arrangement is not possible
if (M % 2 == 1) {
cout << -1 << endl;
return;
}
// Else print all the rows
// such that all elements of each row
// is either odd or even
else {
// Count for the rows
for (int i = 1; i <= M; i++) {
// Initialize num with i
int num = i;
// Count for the columns
for (int j = 1; j <= N; j++) {
cout << num << " ";
// As M is even,
// even + even will give even
// whereas odd + even gives odd
num += M;
}
cout << endl;
}
return;
}
}
// Driver Code
int main()
{
int M = 2, N = 3;
// Function call
validArrangement(M, N);
return 0;
}
Java
// JAVA code to implement the above approach
import java.util.*;
class GFG {
public static void validArrangement(int M, int N)
{
// If N == 1 then the only
// subarray possible is of length 1
// therefore, the mean will
// always be an integer
if (N == 1) {
for (int i = 1; i <= M; i++)
System.out.println(i);
return;
}
// If M is odd the valid
// arrangement is not possible
if (M % 2 == 1) {
System.out.println(-1);
return;
}
// Else print all the rows
// such that all elements of each row
// is either odd or even
else {
// Count for the rows
for (int i = 1; i <= M; i++) {
// Initialize num with i
int num = i;
// Count for the columns
for (int j = 1; j <= N; j++) {
System.out.print(num + " ");
// As M is even,
// even + even will give even
// whereas odd + even gives odd
num += M;
}
System.out.println();
}
return;
}
}
// Driver Code
public static void main(String[] args)
{
int M = 2, N = 3;
// Function call
validArrangement(M, N);
}
}
// This code is contributed by Taranpreet
Python3
# Python3 code to implement the above approach
def validArrangement(M, N):
# If N == 1 then the only
# subarray possible is of length 1
# therefore, the mean will
# always be an integer
if (N == 1):
for i in range(1, M + 1):
print(i)
return
# If M is odd the valid
# arrangement is not possible
if (M % 2 == 1):
print(i)
return
# Else print all the rows
# such that all elements of each row
# is either odd or even
else :
# Count for the rows
for i in range(1,M+1):
# Initialize num with i
num = i
# Count for the columns
for j in range(1,N+1):
print(num,end=" ")
# As M is even,
# even + even will give even
# whereas odd + even gives odd
num += M
print("")
return
# Driver Code
M = 2
N = 3
# Function call
validArrangement(M, N)
# This code is contributed by shinjanpatra
C#
// C# code to implement the above approach
using System;
public class GFG
{
public static void validArrangement(int M, int N)
{
// If N == 1 then the only
// subarray possible is of length 1
// therefore, the mean will
// always be an integer
if (N == 1) {
for (int i = 1; i <= M; i++)
Console.WriteLine(i);
return;
}
// If M is odd the valid
// arrangement is not possible
if (M % 2 == 1) {
Console.WriteLine(-1);
return;
}
// Else print all the rows
// such that all elements of each row
// is either odd or even
else {
// Count for the rows
for (int i = 1; i <= M; i++) {
// Initialize num with i
int num = i;
// Count for the columns
for (int j = 1; j <= N; j++) {
Console.Write(num + " ");
// As M is even,
// even + even will give even
// whereas odd + even gives odd
num += M;
}
Console.WriteLine();
}
return;
}
}
// Driver Code
public static void Main(String[] args) {
int M = 2, N = 3;
// Function call
validArrangement(M, N);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to implement the above approach
function validArrangement(M, N)
{
// If N == 1 then the only
// subarray possible is of length 1
// therefore, the mean will
// always be an integer
if (N == 1) {
for (let i = 1; i <= M; i++)
document.write(i);
return;
}
// If M is odd the valid
// arrangement is not possible
if (M % 2 == 1) {
document.write(-1);
return;
}
// Else print all the rows
// such that all elements of each row
// is either odd or even
else {
// Count for the rows
for (let i = 1; i <= M; i++) {
// Initialize num with i
let num = i;
// Count for the columns
for (let j = 1; j <= N; j++) {
document.write(num," ");
// As M is even,
// even + even will give even
// whereas odd + even gives odd
num += M;
}
document.write("</br>");
}
return;
}
}
// Driver Code
let M = 2, N = 3;
// Function call
validArrangement(M, N);
// This code is contributed by shinjanpatra
</script>
1 3 5 2 4 6
Complejidad temporal: O(MxN)
Espacio auxiliar: O(1)