Número mínimo de cuadrados cuya suma es igual a un número dado N | Conjunto-3

Un número siempre se puede representar como una suma de cuadrados de otros números. Tenga en cuenta que 1 es un cuadrado, y siempre podemos dividir un número como (1*1 + 1*1 + 1*1 + …). Dado un número n, encuentre el número mínimo de cuadrados que suman N.

Ejemplos:

Entrada: N = 13 Salida: 2  Explicación: 13 se puede expresar como, 13 = 3 ² + 2 ² . Por lo tanto, la salida es 2. 

 

Entrada: N = 100 
Salida: 1 
Explicación: 
100 se puede expresar como 100 = 10 ² . Por lo tanto, la salida es 1.

Enfoque ingenuo: para el enfoque [O(N*sqrt(N))], consulte el Conjunto 2 de este artículo .

Enfoque eficiente: para optimizar el enfoque ingenuo, la idea es utilizar el teorema de los cuatro cuadrados de Lagrange y el teorema de los tres cuadrados de Legendre . Los dos teoremas se discuten a continuación: 

El teorema de los cuatro cuadrados de Lagrange , también conocido como la conjetura de Bachet, establece que todo número natural se puede representar como la suma de cuatro cuadrados enteros, donde cada número entero es no negativo. 

El teorema de los tres cuadrados de Legendre establece que un número natural puede representarse como la suma de tres cuadrados de números enteros si y solo si n no tiene la forma: n = 4 ^a (8b+7), para números enteros no negativos a y b . 

Por tanto, se demuestra que el número mínimo de cuadrados para representar cualquier número N sólo puede estar dentro del conjunto {1, 2, 3, 4} . Por lo tanto, solo verificando estos 4 valores posibles, se puede encontrar el número mínimo de cuadrados para representar cualquier número N. Siga los pasos a continuación:

• Si N es un cuadrado perfecto, entonces el resultado es 1 .
• Si N se puede expresar como la suma de dos cuadrados, entonces el resultado es 2 .
• Si N no se puede expresar en la forma de N = 4 ^a (8b+7), donde a y b son números enteros no negativos, entonces el resultado es 3 por el teorema de los tres cuadrados de Legendre. 
• Si no se cumplen todas las condiciones anteriores, entonces por el teorema de los cuatro cuadrados de Lagrange , el resultado es 4 .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if N
// is a perfect square
bool isPerfectSquare(int N)
{
    int floorSqrt = sqrt(N);
 
    return (N == floorSqrt * floorSqrt);
}
 
// Function that returns true check if
// N is sum of three squares
bool legendreFunction(int N)
{
    // Factor out the powers of 4
    while (N % 4 == 0)
        N /= 4;
 
    // N is NOT of the
    // form 4^a * (8b + 7)
    if (N % 8 != 7)
        return true;
    else
        return false;
}
 
// Function that finds the minimum
// number of square whose sum is N
int minSquares(int N)
{
 
    // If N is perfect square
    if (isPerfectSquare(N))
        return 1;
 
    // If N is sum of 2 perfect squares
    for (int i = 1; i * i < N; i++) {
        if (isPerfectSquare(N - i * i))
            return 2;
    }
 
    // If N is sum of 3 perfect squares
    if (legendreFunction(N))
        return 3;
 
    // Otherwise, N is the
    // sum of 4 perfect squares
    return 4;
}
 
// Driver code
int main()
{
    // Given number
    int N = 123;
 
    // Function call
    cout << minSquares(N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function that returns true if N
// is a perfect square
static boolean isPerfectSquare(int N)
{
    int floorSqrt = (int)Math.sqrt(N);
 
    return (N == floorSqrt * floorSqrt);
}
 
// Function that returns true check if
// N is sum of three squares
static boolean legendreFunction(int N)
{
     
    // Factor out the powers of 4
    while (N % 4 == 0)
        N /= 4;
 
    // N is NOT of the
    // form 4^a * (8b + 7)
    if (N % 8 != 7)
        return true;
    else
        return false;
}
 
// Function that finds the minimum
// number of square whose sum is N
static int minSquares(int N)
{
 
    // If N is perfect square
    if (isPerfectSquare(N))
        return 1;
 
    // If N is sum of 2 perfect squares
    for(int i = 1; i * i < N; i++)
    {
        if (isPerfectSquare(N - i * i))
            return 2;
    }
 
    // If N is sum of 3 perfect squares
    if (legendreFunction(N))
        return 3;
 
    // Otherwise, N is the
    // sum of 4 perfect squares
    return 4;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given number
    int N = 123;
 
    // Function call
    System.out.print(minSquares(N));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
from math import sqrt, floor, ceil
 
# Function that returns True if N
# is a perfect square
def isPerfectSquare(N):
   
    floorSqrt = floor(sqrt(N))
    return (N == floorSqrt * floorSqrt)
   
# Function that returns True check if
# N is sum of three squares
def legendreFunction(N):
   
    # Factor out the powers of 4
    while (N % 4 == 0):
        N //= 4
 
    # N is NOT of the
    # form 4^a * (8b + 7)
    if (N % 8 != 7):
        return True
    else:
        return False
 
# Function that finds the minimum
# number of square whose sum is N
def minSquares(N):
   
    # If N is perfect square
    if (isPerfectSquare(N)):
        return 1
 
    # If N is sum of 2 perfect squares
    for i in range(N):
        if i * i < N:
            break
        if (isPerfectSquare(N - i * i)):
            return 2
           
    # If N is sum of 3 perfect squares
    if (legendreFunction(N)):
        return 3
       
    # Otherwise, N is the
    # sum of 4 perfect squares
    return 4
   
# Driver code
if __name__ == '__main__':
 
    # Given number
    N = 123
 
    # Function call
    print(minSquares(N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
 
// Function that returns true if N
// is a perfect square
static bool isPerfectSquare(int N)
{
    int floorSqrt = (int)Math.Sqrt(N);
 
    return (N == floorSqrt * floorSqrt);
}
 
// Function that returns true check
// if N is sum of three squares
static bool legendreFunction(int N)
{
     
    // Factor out the powers of 4
    while (N % 4 == 0)
        N /= 4;
 
    // N is NOT of the
    // form 4^a * (8b + 7)
    if (N % 8 != 7)
        return true;
    else
        return false;
}
 
// Function that finds the minimum
// number of square whose sum is N
static int minSquares(int N)
{
 
    // If N is perfect square
    if (isPerfectSquare(N))
        return 1;
 
    // If N is sum of 2 perfect squares
    for(int i = 1; i * i < N; i++)
    {
        if (isPerfectSquare(N - i * i))
            return 2;
    }
 
    // If N is sum of 3 perfect squares
    if (legendreFunction(N))
        return 3;
 
    // Otherwise, N is the
    // sum of 4 perfect squares
    return 4;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given number
    int N = 123;
 
    // Function call
    Console.Write(minSquares(N));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program for the above approach
 
// Function that returns true if N
// is a perfect square
function isPerfectSquare(N)
{
    let floorSqrt = Math.floor(Math.sqrt(N));
   
    return (N == floorSqrt * floorSqrt);
}
   
// Function that returns true check if
// N is sum of three squares
function legendreFunction(N)
{
       
    // Factor out the powers of 4
    while (N % 4 == 0)
        N = Math.floor(N / 4);
   
    // N is NOT of the
    // form 4^a * (8b + 7)
    if (N % 8 != 7)
        return true;
    else
        return false;
}
   
// Function that finds the minimum
// number of square whose sum is N
function minSquares(N)
{
   
    // If N is perfect square
    if (isPerfectSquare(N))
        return 1;
   
    // If N is sum of 2 perfect squares
    for(let i = 1; i * i < N; i++)
    {
        if (isPerfectSquare(N - i * i))
            return 2;
    }
   
    // If N is sum of 3 perfect squares
    if (legendreFunction(N))
        return 3;
   
    // Otherwise, N is the
    // sum of 4 perfect squares
    return 4;
}
 
// Driver Code
 
    // Given number
    let N = 123;
   
    // Function call
    document.write(minSquares(N));
 
</script>

3

Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)