Números Cuadrables

Dado un entero positivo N, la tarea es verificar si N es un Número Cuadrable o no.

Se dice que un número entero “N” es Cuadrable , si podemos dividir un cuadrado en N Cuadrados que no se superponen (no necesariamente del mismo tamaño).

Ejemplos :

Entrada: N = 1
Salida: “SÍ, 1 es un Número cuadrable”
Explicación: Cualquier Cuadrado satisface este caso.

1 es un número cuadrable 

Entrada: N=4
Salida: “SÍ, 4 es un Número Cuadrable”
Explicación: Un Cuadrado se puede Dividir en 4 Cuadrados.

4 es un número cuadrable

Entrada: N=5
Salida: “NO, 5 no es un Número Cuadrable”
Explicación : Cualquier Cuadrado no se puede Dividir en 5 Cuadrados.

Entrada: N=6 
Salida: “SÍ, 6 es un Número Cuadrable”
Explicación: Un Cuadrado se puede dividir en 6 Cuadrados.

6 es un número cuadrable

Enfoque: Sobre la base de las observaciones mencionadas a continuación, es posible determinar si un número es cuadrable o no:

Observación:

El truco para atrapar aquí es que cada entero positivo N> = 6 , seguramente será cuadrable .

• Esto se puede demostrar mediante hipótesis inductivas . Veamos cómo. 
• Antes de continuar con la prueba por inducción , veamos cómo los números 7 y 8 son cuadráticos (el número 6 es cuadrático, que ya hemos visto en los ejemplos anteriores). Los números 6, 7 y 8 se convertirán en los casos base para probar por inducción.

El número 7 es Cuadrable de la siguiente manera:

7 es un número cuadrable

número 8es cuadrable de la siguiente manera :

8 es un número cuadrable

Casos básicos:

Ya hemos visto que N = 6, 7, 8 son Cuadrables y por lo tanto nuestro Caso Base está Probado.

Prueba por inducción:

Supongamos que los Números “K”, “K – 1” y “K – 2” son cuadrables donde K >= 8. Ahora, veamos como “K + 1” también será cuadrable por Inducción.

Sabemos,

 (K – 2) + 3 = (K + 1)

Por lo tanto, si es posible formar 3 cuadrados más en “(K – 2)” , que es un Número cuadrable, entonces podemos decir que “K + 1” también es cuadrable . Formar 3 cuadrados más en un cuadrado es fácil. Esto se puede lograr simplemente dividiendo el cuadrado en 4 cuadrados pequeños desde el centro . 

Ejemplo a continuación:

Formando 3 Cuadrados Extra en cualquier Cuadrado Dado

Un cuadrado se divide en 4 cuadrados, por lo que se forman 3 nuevos cuadrados. Por tanto, concluyentemente, se prueba que si “K – 2” es Cuadrable, entonces “K+1” también lo es.

Hipótesis inductiva:

Por tanto, por Inducción, podemos decir que nuestros 3 Casos base (N = 6, 7, 8) son suficientes para probar la hipótesis, ya que para Demostrar cualquier Número “X” Cuadrable , estaremos teniendo un Número “X – 3” que es Cuadrable, e inductivamente, «X» también será Cuadrable (ya que 3 Cuadrados pueden Formarse Fácilmente en «X-3» para formar Cuadrados «X» ).

Finalmente, tenemos 6, 7, 8 como números Cuadrables, lo que significa

9 también es cuadrable (como 6 es cuadrable, 6+3=9)
10 también es cuadrable (como 7 es cuadrable, 7+3=10)
11 también es cuadrable (como 8 es cuadrable, 8+3=11)
12 es También Cuadrable (ya que 9 es Cuadrable, 9+3=12)……y así sucesivamente

Por tanto, todo N >= 6 se demuestra Cuadrable.

A continuación se muestra la implementación del enfoque anterior:

// C++ approach for the above problem:
 
#include <iostream>
using namespace std;
 
// Function to find a number is
// Squarable or not
void isSquarable(int N)
{
    if (N < 6) {
        if (N == 1 || N == 4)
            cout << "YES, " << N
          << " is a Squarable Number"
                 << endl;
        else
            cout << "NO, " << N
          << " is not a "
                 << "Squarable Number" << endl;
    }
    else
        cout << "YES, " << N
      << " is a Squarable Number"
             << endl;
}
 
// Drivers code
int main()
{
 
    int N;
 
    isSquarable(1);
    isSquarable(4);
    isSquarable(5);
    isSquarable(6);
    isSquarable(100);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
  // Java approach for the above problem:
 
  // Function to find a number is
  // Squarable or not
  static void isSquarable(int N)
  {
    if (N < 6) {
      if (N == 1 || N == 4)
        System.out.println("YES, " + N + " is a Squarable Number");
      else
        System.out.println("NO, " + N +" is not a " + "Squarable Number");
    }
    else
      System.out.println("YES, " + N + " is a Squarable Number");
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int N;
 
    isSquarable(1);
    isSquarable(4);
    isSquarable(5);
    isSquarable(6);
    isSquarable(100);
  }
 
}
 
// This code is contributed by shinjanpatra

# Python approach for the above problem:
 
# Function to find a number is
# Squarable or not
def isSquarable(N):
    if (N < 6):
        if (N == 1 or N == 4):
            print(f"YES {N} is a Squarable Number");
        else:
            print(f"NO {N} is not a Squarable Number");
    else:
        print(f"YES {N} is a Squarable Number");
 
# Drivers code
isSquarable(1);
isSquarable(4);
isSquarable(5);
isSquarable(6);
isSquarable(100);
     
# This code is contributed by Saurabh Jaiswal

// C# program to check if N is a Squarable Number or not.
using System;
 
public class GFG{
 
  // Function to find a number is
  // Squarable or not
  static void isSquarable(int N)
  {
    if (N < 6) {
      if (N == 1 || N == 4)
        Console.Write("YES, " + N + " is a Squarable Number\n");
      else
        Console.Write("NO, " + N +" is not a " + "Squarable Number\n");
    }
    else
      Console.Write("YES, " + N + " is a Squarable Number\n");
  }
 
  // Driver Code
  static public void Main (){
 
    isSquarable(1);
    isSquarable(4);
    isSquarable(5);
    isSquarable(6);
    isSquarable(100);
  }
}
 
// This code is contributed by shruti456rawal

// JavaScript approach for the above problem:
 
// Function to find a number is
// Squarable or not
function isSquarable(N)
{
    if (N < 6) {
        if (N == 1 || N == 4)
            console.log("YES, "+N+" is a Squarable Number");
        else
        console.log("NO, "+N+" is not a Squarable Number");
    }
    else
    console.log("YES, "+N+" is a Squarable Number");
}
 
// Drivers code
    isSquarable(1);
    isSquarable(4);
    isSquarable(5);
    isSquarable(6);
    isSquarable(100);
     
 // This code is contributed by Ishan Khandelwal

YES, 1 is a Squarable Number
YES, 4 is a Squarable Number
NO, 5 is not a Squarable Number
YES, 6 is a Squarable Number
YES, 100 is a Squarable Number

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)