Dados dos números enteros x e y que representan el número de fila y columna en una array respectivamente, la tarea es encontrar el número entero en la celda (x, y) en la Array rellena en espiral.
Explicación:
El tamaño de la array cambia según la inserción de elementos.
A medida que la fila y las columnas se llenan capa por capa, se formará una array cuadrada a medida que cada fila y columna se agreguen simultáneamente de la siguiente manera:
- Se forma una array cuadrada de tamaño 1 x 1 que tiene un solo elemento 1.
- Una array cuadrada de tamaño 2 x 2 se forma después de la inserción en espiral de los elementos {2, 3, 4} en orden: {
{1, 2},
{4, 3}}- Una array cuadrada de tamaño 3 x 3 se forma después de la inserción en espiral de los elementos {5, 6, 7, 8} en orden: {{1, 2, 9
},
{4, 3, 8},
{5, 6, 7 }}
La imagen de abajo indica una array de 4*4 generada siguiendo los pasos anteriores:
Ejemplos:
Entrada: X = 2, Y = 3
Salida: 8
Explicación:
El elemento en la fila 2 y la columna 3 es 8.Entrada: X = 5, Y = 4
Salida: 20
Explicación: El elemento en la fila 5 y la columna 4 es 20.
Enfoque:
para resolver el problema, se debe comprender la lógica detrás de la array espiral dada. Los siguientes son los posibles casos que deben ser considerados:
- Caso 1: Si y > x & y es impar
El elemento en (x, y) es igual a y 2 – x +1
Ilustración:
y = 3, x = 1
y 2 – x +1 = 9 – 1 + 1 = 9
Elemento presente en (1, 3) = 9.
- Caso 2: Si y > x & y es par
El elemento en (x, y) es igual a (y – 1) 2 + x
Ilustración:
y = 4, x = 1
(y – 1) 2 + x = 9 + 1 = 10
Elemento presente en (1, 4) = 10.
- Caso 3: Si x ≥ y & x es par
El elemento en (x, y) es igual a x 2 – y +1
Ilustración:
y = 1, x = 4
x 2 – y + 1 = 16 – 1 + 1 = 16
Elemento presente en (4, 1) = 16.
- Caso 4: Si x ≥ y & x es impar
El elemento en (x, y) es igual a (x – 1) 2 + y
Ilustración:
y = 2, x = 3
(x – 1) 2 + y = 4 + 2 = 6
Elemento presente en (3, 2) = 6.
Por lo tanto, para resolver el problema, necesitamos evaluar e imprimir el resultado de la ecuación correspondiente a la condición que satisfacen las x e y dadas .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the element
// at given position in spirally
// filled matrix
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// element at (x, y)
int SpiralElement(int x, int y)
{
int r;
// If y is greater
if (x < y) {
// If y is odd
if (y % 2 == 1) {
r = y * y;
return (r - x + 1);
}
// If y is even
else {
r = (y - 1) * (y - 1);
return (r + x);
}
}
else {
// If x is even
if (x % 2 == 0) {
r = x * x;
return (r - y + 1);
}
// If x is odd
else {
r = (x - 1) * (x - 1);
return (r + y);
}
}
}
// Driver Code
int main()
{
int x = 2, y = 3;
cout << SpiralElement(x, y);
return 0;
}
Java
// Java program to find the element
// at given position in spirally
// filled matrix
import java.util.*;
class GFG{
// Function to return the
// element at (x, y)
static int SpiralElement(int x, int y)
{
int r;
// If y is greater
if (x < y)
{
// If y is odd
if (y % 2 == 1)
{
r = y * y;
return (r - x + 1);
}
// If y is even
else
{
r = (y - 1) * (y - 1);
return (r + x);
}
}
else
{
// If x is even
if (x % 2 == 0)
{
r = x * x;
return (r - y + 1);
}
// If x is odd
else
{
r = (x - 1) * (x - 1);
return (r + y);
}
}
}
// Driver code
public static void main(String[] args)
{
int x = 2, y = 3;
System.out.println(SpiralElement(x, y));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the element # at given position in spirally # filled matrix # Function to return the # element at (x, y) def SpiralElement(x, y): r = 0 # If y is greater if (x < y): # If y is odd if (y % 2 == 1): r = y * y return (r - x + 1) # If y is even else: r = (y - 1) * (y - 1) return (r + x) else: # If x is even if (x % 2 == 0): r = x * x return (r - y + 1) # If x is odd else: r = (x - 1) * (x - 1) return (r + y) # Driver code if __name__ == '__main__': x = 2 y = 3 print(SpiralElement(x, y)) # This code is contributed by Amit Katiyar
C#
// C# program to find the element
// at given position in spirally
// filled matrix
using System;
class GFG{
// Function to return the
// element at (x, y)
static int SpiralElement(int x, int y)
{
int r;
// If y is greater
if (x < y)
{
// If y is odd
if (y % 2 == 1)
{
r = y * y;
return (r - x + 1);
}
// If y is even
else
{
r = (y - 1) * (y - 1);
return (r + x);
}
}
else
{
// If x is even
if (x % 2 == 0)
{
r = x * x;
return (r - y + 1);
}
// If x is odd
else
{
r = (x - 1) * (x - 1);
return (r + y);
}
}
}
// Driver code
static public void Main()
{
int x = 2, y = 3;
Console.WriteLine(SpiralElement(x, y));
}
}
// This code is contributed by offbeat
Javascript
<script>
// javascript program to find the element
// at given position in spirally
// filled matrix
// Function to return the
// element at (x, y)
function SpiralElement(x , y) {
var r;
// If y is greater
if (x < y) {
// If y is odd
if (y % 2 == 1) {
r = y * y;
return (r - x + 1);
}
// If y is even
else {
r = (y - 1) * (y - 1);
return (r + x);
}
} else {
// If x is even
if (x % 2 == 0) {
r = x * x;
return (r - y + 1);
}
// If x is odd
else {
r = (x - 1) * (x - 1);
return (r + y);
}
}
}
// Driver code
var x = 2, y = 3;
document.write(SpiralElement(x, y));
// This code contributed by gauravrajput1
</script>
8
Complejidad temporal: O(1)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por chahattekwani71 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA