Dados dos números enteros N y M que denotan una array de tamaño N*M , la tarea es formar una array siguiendo los siguientes criterios y hacer que el elemento máximo sea el mínimo posible:
- Los elementos de cada fila están en progresión aritmética de izquierda a derecha.
- Los elementos de cada columna también están en progresión aritmética de arriba a abajo.
- Las diferencias comunes entre todas las filas y columnas son únicas.
Nota: Si hay múltiples respuestas posibles, imprima cualquiera de ellas.
Ejemplos:
Entrada: N = 2, N = 4
Salida: {{1, 2, 3, 4}, {4, 6, 8, 10}}
Explicación: En lo anterior, la diferencia común para la primera fila es 1.
La diferencia común para la segunda fila es 2.
La diferencia común para las columnas es 3, 4, 5 y 6 respectivamente.
Entonces, todas las diferencias comunes son únicas y
el valor máximo es 10, que es el mínimo posible.Entrada: A = 1, B = 3
Salida: {1, 2, 3}
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Observaciones:
Para minimizar el elemento máximo, necesitamos hacer que la diferencia común sea mínima a lo largo del lado más largo . Debemos partir de la mínima diferencia común de 1 para ese lado. Luego incrementa la diferencia común en 1 a lo largo de esos lados. Después de eso, piense en la diferencia común para el otro lado.
Por ejemplo, si hay 2 filas y 4 columnas, hay más columnas que filas. Cada fila tiene 4 elementos. Por lo tanto, la diferencia común para la primera fila deberíamos establecerla como 1, luego para la segunda fila como 2.
Después de recorrer la fila, establezca la diferencia común para la primera columna en 3 y continúe con esto.
Siga los pasos mencionados a continuación para implementar la idea anterior:
- Primero, marque N ≤ M o no:
- Si lo es, entonces:
- Los elementos de la primera fila aumentan estrictamente de izquierda a derecha con una diferencia común fija de 1 , incremente de manera similar la diferencia común en 1 y siga el mismo proceso para cada fila.
- Y luego, para la primera columna , los elementos aumentan estrictamente de arriba a abajo con una diferencia común fija A+1 y la diferencia común se incrementa en 1 para cada columna siguiente.
- Si no entonces:
- Los elementos de la primera columna aumentan estrictamente de arriba a abajo con una diferencia común fija de 1 e incrementan la diferencia común en 1 para cada una de las siguientes columnas y siguen el mismo proceso para ellas.
- Para la primera fila , los elementos aumentan estrictamente de izquierda a derecha con una diferencia común fija B+1 y la diferencia común se incrementa en 1 para cada una de las siguientes filas.
- Si lo es, entonces:
- Devuelva la array así formada como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function to find the matrix
void matrix(int A, int B)
{
// Number of row is less than or
// equal to number of column
if (A <= B) {
for (int j = 0; j < A; j++) {
for (int k = 0; k < B; k++) {
cout << 1 + (A + 1) * j + (j + 1) * k
<< " ";
}
cout << endl;
}
}
// Number of column is less
// than number of row
else {
for (int j = 0; j < A; j++) {
for (int k = 0; k < B; k++) {
cout << 1 + (B + 1) * k + (k + 1) * j
<< " ";
}
cout << endl;
}
}
}
// Driver Code
int main()
{
int A = 2;
int B = 4;
// Function call
matrix(A, B);
return 0;
}
// This code is contributed by aarohirai2616.
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the matrix
public static ArrayList<ArrayList<Integer> >
matrix(int A, int B)
{
ArrayList<ArrayList<Integer> > res
= new ArrayList<ArrayList<Integer> >();
// Number of row is less than or
// equal to number of column
if (A <= B) {
for (int j = 0; j < A; j++) {
ArrayList<Integer> temp
= new ArrayList<Integer>();
for (int k = 0; k < B; k++) {
temp.add(1 + (A + 1) * j + (j + 1) * k);
}
res.add(temp);
}
}
// Number of column is less
// than number of row
else {
for (int j = 0; j < A; j++) {
ArrayList<Integer> temp
= new ArrayList<Integer>();
for (int k = 0; k < B; k++) {
temp.add(1 + (B + 1) * k + (k + 1) * j);
}
res.add(temp);
}
}
return res;
}
// Driver code
public static void main(String[] args)
{
int A = 2;
int B = 4;
// Function call
ArrayList<ArrayList<Integer> > ans = matrix(A, B);
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans.get(i).size(); j++)
System.out.print(ans.get(i).get(j) + " ");
System.out.println();
}
}
}
Python3
# Python3 code to implement the approach # Function to find the matrix def matrix(A, B): # Number of row is less than or # equal to number of column if (A <= B): for j in range(A): for k in range(B): print(1 + (A + 1) * j + (j + 1) * k, end=" ") print() # Number of column is less # than number of row else: for j in range(A): for k in range(B): print(1 + (B + 1) * k + (k + 1) * j, end=" ") print() # Driver Code if __name__ == "__main__": A = 2 B = 4 # Function call matrix(A, B) # This code is contributed by AnkThon
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the matrix
public static List<List<int> > matrix(int A, int B)
{
List<List<int> > res = new List<List<int> >();
// Number of row is less than or
// equal to number of column
if (A <= B) {
for (int j = 0; j < A; j++) {
List<int> temp = new List<int>();
for (int k = 0; k < B; k++) {
temp.Add(1 + (A + 1) * j + (j + 1) * k);
}
res.Add(temp);
}
}
// Number of column is less
// than number of row
else {
for (int j = 0; j < A; j++) {
List<int> temp = new List<int>();
for (int k = 0; k < B; k++) {
temp.Add(1 + (B + 1) * k + (k + 1) * j);
}
res.Add(temp);
}
}
return res;
}
// Driver code
public static void Main(string[] args)
{
int A = 2;
int B = 4;
// Function call
List<List<int> > ans = matrix(A, B);
for (int i = 0; i < ans.Count; i++) {
for (int j = 0; j < ans[i].Count; j++)
Console.Write(ans[i][j] + " ");
Console.WriteLine();
}
}
}
// This code is contributed by phasing17
Javascript
// Javascript code to implement the approach
<script>
// Function to find the matrix
function matrix(A,B)
{
// Number of row is less than or
// equal to number of column
if (A <= B) {
for (let j = 0; j < A; j++) {
for (let k = 0; k < B; k++) {
let ans=1 + (A + 1) * j + (j + 1) * k;
document.write(ans+" ");
}
document.write( "<br>");
}
}
// Number of column is less
// than number of row
else {
for (let j = 0; j < A; j++) {
for (let k = 0; k < B; k++) {
let ans1=1 + (B + 1) * k + (k + 1) * j;
document.write(ans1+" ");
}
document.write( "<br>");
}
}
}
// Driver Code
let A = 2;
let B = 4;
// Function call
matrix(A, B);
// This code is contributed by satwik4409.
</script>
1 2 3 4 4 6 8 10
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por aarohirai2616 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA