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 X.
Ejemplos:
Entrada: n = 100
Salida: 1
Explicación:
100 se puede escribir como 10 2 . Tenga en cuenta que 100 también se puede escribir como 5 2 + 5 2 + 5 2 + 5 2 , pero esta representación requiere 4 cuadrados.Entrada: n = 6
Salida : 3
La idea es sencilla, partimos de 1 y vamos a un número cuyo cuadrado sea menor o igual a n. Para todo número x recurrimos para nx. A continuación se muestra la fórmula recursiva.
If n = 1 and x*x <= n
A continuación se muestra una solución recursiva simple basada en la fórmula recursiva anterior.
C++
// A naive recursive C++
// program to find minimum
// number of squares whose sum
// is equal to a given number
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum
// squares that sum to n
int getMinSquares(unsigned int n)
{
// base cases
// if n is perfect square then
// Minimum squares required is 1
// (144 = 12^2)
if (sqrt(n) - floor(sqrt(n)) == 0)
return 1;
if (n <= 3)
return n;
// getMinSquares rest of the
// table using recursive
// formula
// Maximum squares required
// is n (1*1 + 1*1 + ..)
int res = n;
// Go through all smaller numbers
// to recursively find minimum
for (int x = 1; x <= n; x++)
{
int temp = x * x;
if (temp > n)
break;
else
res = min(res, 1 + getMinSquares
(n - temp));
}
return res;
}
// Driver code
int main()
{
cout << getMinSquares(6);
return 0;
}
Java
// A naive recursive JAVA
// program to find minimum
// number of squares whose
// sum is equal to a given number
class squares
{
// Returns count of minimum
// squares that sum to n
static int getMinSquares(int n)
{
// base cases
if (n <= 3)
return n;
// getMinSquares rest of the
// table using recursive
// formula
// Maximum squares required is
int res = n;
// n (1*1 + 1*1 + ..)
// Go through all smaller numbers
// to recursively find minimum
for (int x = 1; x <= n; x++)
{
int temp = x * x;
if (temp > n)
break;
else
res = Math.min(res, 1 +
getMinSquares(n - temp));
}
return res;
}
// Driver code
public static void main(String args[])
{
System.out.println(getMinSquares(6));
}
}
/* This code is contributed by Rajat Mishra */
Python3
# A naive recursive Python program to # find minimum number of squares whose # sum is equal to a given number # Returns count of minimum squares # that sum to n def getMinSquares(n): # base cases if n <= 3: return n; # getMinSquares rest of the table # using recursive formula # Maximum squares required # is n (1 * 1 + 1 * 1 + ..) res = n # Go through all smaller numbers # to recursively find minimum for x in range(1, n + 1): temp = x * x; if temp > n: break else: res = min(res, 1 + getMinSquares(n - temp)) return res; # Driver code print(getMinSquares(6)) # This code is contributed by nuclode
C#
// A naive recursive C# program
// to find minimum number of
// squares whose sum is equal
// to a given number
using System;
class GFG
{
// Returns count of minimum
// squares that sum to n
static int getMinSquares(int n)
{
// base cases
if (n <= 3)
return n;
// getMinSquares rest of the
// table using recursive
// formula
// Maximum squares required is
// n (1*1 + 1*1 + ..)
int res = n;
// Go through all smaller numbers
// to recursively find minimum
for (int x = 1; x <= n; x++)
{
int temp = x * x;
if (temp > n)
break;
else
res = Math.Min(res, 1 +
getMinSquares(n - temp));
}
return res;
}
// Driver Code
public static void Main()
{
Console.Write(getMinSquares(6));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// A naive recursive PHP program
// to find minimum number of
// squares whose sum is equal
// to a given number
// Returns count of minimum
// squares that sum to n
function getMinSquares($n)
{
// base cases
if ($n <= 3)
return $n;
// getMinSquares rest of the
// table using recursive formula
// Maximum squares required
// is n (1*1 + 1*1 + ..)
$res = $n;
// Go through all smaller numbers
// to recursively find minimum
for ($x = 1; $x <= $n; $x++)
{
$temp = $x * $x;
if ($temp > $n)
break;
else
$res = min($res, 1 +
getMinSquares($n -
$temp));
}
return $res;
}
// Driver Code
echo getMinSquares(6);
// This code is contributed
// by nitin mittal.
?>
Javascript
<script>
// A naive recursive Javascript program
// to find minimum number of squares
// whose sum is equal to a given number
// Returns count of minimum
// squares that sum to n
function getMinSquares(n)
{
// base cases
if (n <= 3)
return n;
// getMinSquares rest of the
// table using recursive
// formula
// Maximum squares required is
// n (1*1 + 1*1 + ..)
let res = n;
// Go through all smaller numbers
// to recursively find minimum
for(let x = 1; x <= n; x++)
{
let temp = x * x;
if (temp > n)
break;
else
res = Math.min(res,
1 + getMinSquares(n - temp));
}
return res;
}
// Driver code
document.write(getMinSquares(6));
// This code is contributed by suresh07
</script>
Producción
3
La complejidad temporal de la solución anterior es exponencial. Si dibujamos el árbol de recursión, podemos observar que muchos subproblemas se resuelven una y otra vez. Por ejemplo, cuando partimos de n = 6, podemos llegar a 4 restando 1 2 veces y restando 2 1 vez. Entonces, el subproblema para 4 se llama dos veces.
Dado que se vuelven a llamar los mismos subproblemas, este problema tiene la propiedad Superposición de subproblemas. Entonces, el problema de suma cuadrada mínima tiene ambas propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de Programación Dinámica (DP) , los recálculos de los mismos subproblemas se pueden evitar construyendo una tabla de array temporal [][] de forma ascendente. A continuación se muestra una solución basada en programación dinámica.
C++
// A dynamic programming based
// C++ program to find minimum
// number of squares whose sum
// is equal to a given number
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum
// squares that sum to n
int getMinSquares(int n)
{
// We need to check base case
// for n i.e. 0,1,2
// the below array creation
// will go OutOfBounds.
if(n<=3)
return n;
// Create a dynamic
// programming table
// to store sq
int* dp = new int[n + 1];
// getMinSquares table
// for base case entries
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// getMinSquares rest of the
// table using recursive
// formula
for (int i = 4; i <= n; i++)
{
// max value is i as i can
// always be represented
// as 1*1 + 1*1 + ...
dp[i] = i;
// Go through all smaller numbers to
// to recursively find minimum
for (int x = 1; x <= ceil(sqrt(i)); x++)
{
int temp = x * x;
if (temp > i)
break;
else
dp[i] = min(dp[i], 1 +
dp[i - temp]);
}
}
// Store result and free dp[]
int res = dp[n];
delete[] dp;
return res;
}
// Driver code
int main()
{
cout << getMinSquares(6);
return 0;
}
Java
// A dynamic programming based
// JAVA program to find minimum
// number of squares whose sum
// is equal to a given number
class squares
{
// Returns count of minimum
// squares that sum to n
static int getMinSquares(int n)
{
// We need to add a check
// here for n. If user enters
// 0 or 1 or 2
// the below array creation
// will go OutOfBounds.
if (n <= 3)
return n;
// Create a dynamic programming
// table
// to store sq
int dp[] = new int[n + 1];
// getMinSquares table for
// base case entries
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// getMinSquares rest of the
// table using recursive
// formula
for (int i = 4; i <= n; i++)
{
// max value is i as i can
// always be represented
// as 1*1 + 1*1 + ...
dp[i] = i;
// Go through all smaller numbers to
// to recursively find minimum
for (int x = 1; x <= Math.ceil(
Math.sqrt(i)); x++)
{
int temp = x * x;
if (temp > i)
break;
else
dp[i] = Math.min(dp[i], 1
+ dp[i - temp]);
}
}
// Store result and free dp[]
int res = dp[n];
return res;
}
// Driver Code
public static void main(String args[])
{
System.out.println(getMinSquares(6));
}
} /* This code is contributed by Rajat Mishra */
Python3
# A dynamic programming based Python # program to find minimum number of # squares whose sum is equal to a # given number from math import ceil, sqrt # Returns count of minimum squares # that sum to n def getMinSquares(n): # Create a dynamic programming table # to store sq and getMinSquares table # for base case entries dp = [0, 1, 2, 3] # getMinSquares rest of the table # using recursive formula for i in range(4, n + 1): # max value is i as i can always # be represented as 1 * 1 + 1 * 1 + ... dp.append(i) # Go through all smaller numbers # to recursively find minimum for x in range(1, int(ceil(sqrt(i))) + 1): temp = x * x; if temp > i: break else: dp[i] = min(dp[i], 1 + dp[i-temp]) # Store result return dp[n] # Driver code print(getMinSquares(6)) # This code is contributed by nuclode
C#
// A dynamic programming based
// C# program to find minimum
// number of squares whose sum
// is equal to a given number
using System;
class squares
{
// Returns count of minimum
// squares that sum to n
static int getMinSquares(int n)
{
// We need to add a check here
// for n. If user enters 0 or 1 or 2
// the below array creation will go
// OutOfBounds.
if (n <= 3)
return n;
// Create a dynamic programming
// table to store sq
int[] dp = new int[n + 1];
// getMinSquares table for base
// case entries
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// getMinSquares for rest of the
// table using recursive formula
for (int i = 4; i <= n; i++)
{
// max value is i as i can
// always be represented
// as 1 * 1 + 1 * 1 + ...
dp[i] = i;
// Go through all smaller numbers to
// to recursively find minimum
for (int x = 1; x <= Math.Ceiling(
Math.Sqrt(i)); x++)
{
int temp = x * x;
if (temp > i)
break;
else
dp[i] = Math.Min(dp[i], 1 +
dp[i - temp]);
}
}
// Store result and free dp[]
int res = dp[n];
return res;
}
// Driver Code
public static void Main(String[] args)
{
Console.Write(getMinSquares(6));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// A dynamic programming based
// PHP program to find minimum
// number of squares whose sum
// is equal to a given number
// Returns count of minimum
// squares that sum to n
function getMinSquares($n)
{
// Create a dynamic programming
// table to store sq
$dp;
// getMinSquares table for
// base case entries
$dp[0] = 0;
$dp[1] = 1;
$dp[2] = 2;
$dp[3] = 3;
// getMinSquares rest of the
// table using recursive formula
for ($i = 4; $i <= $n; $i++)
{
// max value is i as i can
// always be represented
// as 1*1 + 1*1 + ...
$dp[$i] = $i;
// Go through all smaller
// numbers to recursively
// find minimum
for ($x = 1; $x <= ceil(sqrt($i));
$x++)
{
$temp = $x * $x;
if ($temp > $i)
break;
else $dp[$i] = min($dp[$i],
(1 + $dp[$i - $temp]));
}
}
// Store result
// and free dp[]
$res = $dp[$n];
// delete $dp;
return $res;
}
// Driver Code
echo getMinSquares(6);
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
// A dynamic programming based
// javascript program to find minimum
// number of squares whose sum
// is equal to a given number
// Returns count of minimum
// squares that sum to n
function getMinSquares( n)
{
// We need to add a check here
// for n. If user enters 0 or 1 or 2
// the below array creation will go
// OutOfBounds.
if (n <= 3)
return n;
// Create a dynamic programming
// table to store sq
var dp = new Array(n + 1);
// getMinSquares table for base
// case entries
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// getMinSquares for rest of the
// table using recursive formula
for (var i = 4; i <= n; i++)
{
// max value is i as i can
// always be represented
// as 1 * 1 + 1 * 1 + ...
dp[i] = i;
// Go through all smaller numbers to
// to recursively find minimum
for (var x = 1; x <= Math.ceil(
Math.sqrt(i)); x++)
{
var temp = x * x;
if (temp > i)
break;
else
dp[i] = Math.min(dp[i], 1 +
dp[i - temp]);
}
}
// Store result and free dp[]
var res = dp[n];
return res;
}
// Driver Code
document.write(getMinSquares(6));
</script>
Producción
3
Gracias a Gaurav Ahirwar por sugerir esta solución.
Otro enfoque: (USO DE LA MEMOIZACIÓN)
El problema también se puede resolver utilizando el método de memorización (programación dinámica).
A continuación se muestra la implementación:
C++
#include <bits/stdc++.h>
using namespace std;
int minCount(int n)
{
int* minSquaresRequired = new int[n + 1];
minSquaresRequired[0] = 0;
minSquaresRequired[1] = 1;
for (int i = 2; i <= n; ++i)
{
minSquaresRequired[i] = INT_MAX;
for (int j = 1; i - (j * j) >= 0; ++j)
{
minSquaresRequired[i]
= min(minSquaresRequired[i],
minSquaresRequired[i - (j * j)]);
}
minSquaresRequired[i] += 1;
}
int result = minSquaresRequired[n];
delete[] minSquaresRequired;
return result;
}
// Driver code
int main()
{
cout << minCount(6);
return 0;
}
Java
import java.util.*;
class GFG {
static int minCount(int n)
{
int[] minSquaresRequired = new int[n + 1];
minSquaresRequired[0] = 0;
minSquaresRequired[1] = 1;
for (int i = 2; i <= n; ++i)
{
minSquaresRequired[i] = Integer.MAX_VALUE;
for (int j = 1; i - (j * j) >= 0; ++j)
{
minSquaresRequired[i] = Math.min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]);
}
minSquaresRequired[i] += 1;
}
int result = minSquaresRequired[n];
return result;
}
// Driver code
public static void main(String[] args) {
System.out.print(minCount(6));
}
}
// This code contributed by gauravrajput1
Python3
import sys def minCount(n): minSquaresRequired = [0 for i in range(n+1)]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for i in range(2,n+1): minSquaresRequired[i] = sys.maxsize; j = 1 for j in range(1,i - (j * j)): if(i - (j * j) >= 0): minSquaresRequired[i] = min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); else: break minSquaresRequired[i] += 1; result = minSquaresRequired[n]; return result; # Driver code if __name__ == '__main__': print(minCount(6)); # This code is contributed by umadevi9616
C#
using System;
class GFG {
static int minCount(int n)
{
int[] minSquaresRequired = new int[n + 1];
minSquaresRequired[0] = 0;
minSquaresRequired[1] = 1;
for (int i = 2; i <= n; ++i)
{
minSquaresRequired[i] = Int32.MaxValue;
for (int j = 1; i - (j * j) >= 0; ++j)
{
minSquaresRequired[i] = Math.Min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]);
}
minSquaresRequired[i] += 1;
}
int result = minSquaresRequired[n];
return result;
}
// Driver code
public static void Main(String[] args) {
Console.Write(minCount(6));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program to implement
// the above approach
function minCount(n)
{
let minSquaresRequired = new Array(n + 1);
minSquaresRequired[0] = 0;
minSquaresRequired[1] = 1;
for (let i = 2; i <= n; ++i) {
minSquaresRequired[i] = Number.MAX_VALUE;
for (let j = 1; i - (j * j) >= 0; ++j) {
minSquaresRequired[i]
= Math.min(minSquaresRequired[i],
minSquaresRequired[i - (j * j)]);
}
minSquaresRequired[i] += 1;
}
let result = minSquaresRequired[n];
return result;
}
// Driver code
document.write(minCount(6));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Otro enfoque:
este problema también se puede resolver mediante el uso de gráficos. Aquí está la idea básica de cómo se puede hacer.
Usaremos BFS (búsqueda primero en amplitud) para encontrar el número mínimo de pasos desde un valor dado de n a 0.
Entonces, para cada Node, empujaremos la siguiente ruta válida posible que aún no se ha visitado en una cola y,
y si llega al Node 0, actualizaremos nuestra respuesta si es menor que la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum
// squares that sum to n
int numSquares(int n)
{
// Creating visited vector
// of size n + 1
vector<int> visited(n + 1,0);
// Queue of pair to store node
// and number of steps
queue< pair<int,int> >q;
// Initially ans variable is
// initialized with inf
int ans = INT_MAX;
// Push starting node with 0
// 0 indicate current number
// of step to reach n
q.push({n,0});
// Mark starting node visited
visited[n] = 1;
while(!q.empty())
{
pair<int,int> p;
p = q.front();
q.pop();
// If node reaches its destination
// 0 update it with answer
if(p.first == 0)
ans=min(ans, p.second);
// Loop for all possible path from
// 1 to i*i <= current node(p.first)
for(int i = 1; i * i <= p.first; i++)
{
// If we are standing at some node
// then next node it can jump to will
// be current node-
// (some square less than or equal n)
int path=(p.first - (i*i));
// Check if it is valid and
// not visited yet
if(path >= 0 && ( !visited[path]
|| path == 0))
{
// Mark visited
visited[path]=1;
// Push it it Queue
q.push({path,p.second + 1});
}
}
}
// Return ans to calling function
return ans;
}
// Driver code
int main()
{
cout << numSquares(12);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.awt.Point;
class GFG
{
// Function to count minimum
// squares that sum to n
public static int numSquares(int n)
{
// Creating visited vector
// of size n + 1
int visited[] = new int[n + 1];
// Queue of pair to store node
// and number of steps
Queue<Point> q = new LinkedList<>();
// Initially ans variable is
// initialized with inf
int ans = Integer.MAX_VALUE;
// Push starting node with 0
// 0 indicate current number
// of step to reach n
q.add(new Point(n, 0));
// Mark starting node visited
visited[n] = 1;
while(q.size() != 0)
{
Point p = q.peek();
q.poll();
// If node reaches its destination
// 0 update it with answer
if(p.x == 0)
ans = Math.min(ans, p.y);
// Loop for all possible path from
// 1 to i*i <= current node(p.first)
for(int i = 1; i * i <= p.x; i++)
{
// If we are standing at some node
// then next node it can jump to will
// be current node-
// (some square less than or equal n)
int path = (p.x - (i * i));
// Check if it is valid and
// not visited yet
if(path >= 0 && (visited[path] == 0 || path == 0))
{
// Mark visited
visited[path] = 1;
// Push it it Queue
q.add(new Point(path, p.y + 1));
}
}
}
// Return ans to calling function
return ans;
}
// Driver code
public static void main(String[] args)
{
System.out.println(numSquares(12));
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program for the above approach import sys # Function to count minimum # squares that sum to n def numSquares(n) : # Creating visited vector # of size n + 1 visited = [0]*(n + 1) # Queue of pair to store node # and number of steps q = [] # Initially ans variable is # initialized with inf ans = sys.maxsize # Push starting node with 0 # 0 indicate current number # of step to reach n q.append([n, 0]) # Mark starting node visited visited[n] = 1 while(len(q) > 0) : p = q[0] q.pop(0) # If node reaches its destination # 0 update it with answer if(p[0] == 0) : ans = min(ans, p[1]) # Loop for all possible path from # 1 to i*i <= current node(p.first) i = 1 while i * i <= p[0] : # If we are standing at some node # then next node it can jump to will # be current node- # (some square less than or equal n) path = p[0] - i * i # Check if it is valid and # not visited yet if path >= 0 and (visited[path] == 0 or path == 0) : # Mark visited visited[path] = 1 # Push it it Queue q.append([path,p[1] + 1]) i += 1 # Return ans to calling function return ans print(numSquares(12)) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
public class Point
{
public int x, y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Function to count minimum
// squares that sum to n
public static int numSquares(int n)
{
// Creating visited vector
// of size n + 1
int []visited = new int[n + 1];
// Queue of pair to store node
// and number of steps
Queue q = new Queue();
// Initially ans variable is
// initialized with inf
int ans = 1000000000;
// Push starting node with 0
// 0 indicate current number
// of step to reach n
q.Enqueue(new Point(n, 0));
// Mark starting node visited
visited[n] = 1;
while(q.Count != 0)
{
Point p = (Point)q.Dequeue();
// If node reaches its destination
// 0 update it with answer
if (p.x == 0)
ans = Math.Min(ans, p.y);
// Loop for all possible path from
// 1 to i*i <= current node(p.first)
for(int i = 1; i * i <= p.x; i++)
{
// If we are standing at some node
// then next node it can jump to will
// be current node-
// (some square less than or equal n)
int path = (p.x - (i * i));
// Check if it is valid and
// not visited yet
if (path >= 0 && (visited[path] == 0 ||
path == 0))
{
// Mark visited
visited[path] = 1;
// Push it it Queue
q.Enqueue(new Point(path, p.y + 1));
}
}
}
// Return ans to calling function
return ans;
}
// Driver code
public static void Main(string[] args)
{
Console.Write(numSquares(12));
}
}
// This code is contributed by rutvik_56
Javascript
// JavaScript program for the above approach
// Function to count minimum
// squares that sum to n
function numSquares(n)
{
// Creating visited vector
// of size n + 1
let visited = new Array(n + 1).fill(0);
// Queue of pair to store node
// and number of steps
let q = [];
// Initially ans variable is
// initialized with inf
let ans = Number.MAX_SAFE_INTEGER;
// Push starting node with 0
// 0 indicate current number
// of step to reach n
q.push([n, 0]);
// Mark starting node visited
visited[n] = 1;
while(q.length > 0)
{
let p = q[0];
q.shift();
// If node reaches its destination
// 0 update it with answer
if(p[0] == 0)
ans = Math.min(ans, p[1]);
// Loop for all possible path from
// 1 to i*i <= current node(p.first)
let i = 1;
while (i * i <= p[0])
{
// If we are standing at some node
// then next node it can jump to will
// be current node-
// (some square less than or equal n)
let path = p[0] - i * i;
// Check if it is valid and
// not visited yet
if (path >= 0 && (visited[path] == 0 || path == 0) )
{
// Mark visited
visited[path] = 1;
// Push it it Queue
q.push([path,p[1] + 1]);
}
i += 1;
}
}
// Return ans to calling function
return ans;
}
console.log(numSquares(12));
// This code is contributed by phasing17
Producción
3
La complejidad temporal del problema anterior es O(n)*sqrt(n), que es mejor que el enfoque recursivo.
Además, es una excelente manera de comprender cómo funciona BFS (búsqueda primero en amplitud).
Escriba un si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Otro enfoque:
Este problema también se puede resolver mediante la programación dinámica (enfoque ascendente). La idea es como el cambio de moneda 2 (en el que necesitamos decir el número mínimo de monedas para hacer una cantidad a partir de una array dada de monedas []), aquí una array de todos los cuadrados perfectos menores o iguales a n puede ser reemplazada por monedas [] la array y la cantidad se pueden reemplazar por n. Solo vea esto como un problema de mochila ilimitado, veamos un ejemplo:
Para la entrada dada n = 6, haremos una array hasta 4, arr: [1,4]
Aquí, la respuesta será (4 + 1 + 1 = 6), es decir, 3.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum
// squares that sum to n
int numSquares(int n)
{
//Making the array of perfect squares less than or equal to n
vector <int> arr;
int i = 1;
while(i*i <= n){
arr.push_back(i*i);
i++;
}
//A dp array which will store minimum number of perfect squares
//required to make n from i at i th index
vector <int> dp(n+1, INT_MAX);
dp[n] = 0;
for(int i = n-1; i>=0; i--){
//checking from i th value to n value minimum perfect squares required
for(int j = 0; j<arr.size(); j++){
//check if index doesn't goes out of bound
if(i + arr[j] <= n){
dp[i] = min(dp[i], dp[i+arr[j]]);
}
}
//from current to go to min step one i we need to take one step
dp[i]++;
}
return dp[0];
}
// Driver code
int main()
{
cout << numSquares(12);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count minimum
// squares that sum to n
static int numSquares(int n)
{
// Making the array of perfect squares less than or equal to n
Vector <Integer> arr = new Vector<>();
int k = 1;
while(k * k <= n){
arr.add(k * k);
k++;
}
// A dp array which will store minimum number of perfect squares
// required to make n from i at i th index
int []dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[n] = 0;
for(int i = n - 1; i >= 0; i--)
{
// checking from i th value to n value minimum perfect squares required
for(int j = 0; j < arr.size(); j++)
{
// check if index doesn't goes out of bound
if(i + arr.elementAt(j) <= n)
{
dp[i] = Math.min(dp[i], dp[i+arr.elementAt(j)]);
}
}
// from current to go to min step one i we need to take one step
dp[i]++;
}
return dp[0];
}
// Driver code
public static void main(String[] args)
{
System.out.print(numSquares(12));
}
}
// This code is contributed by umadevi9616.
Python3
# Python program for the above approach import sys # Function to count minimum # squares that sum to n def numSquares(n): # Making the array of perfect squares less than or equal to n arr = []; k = 1; while (k * k <= n): arr.append(k * k); k += 1; # A dp array which will store minimum number of perfect squares # required to make n from i at i th index dp = [sys.maxsize for i in range(n+1)]; dp[n] = 0; for i in range(n-1, -1,-1): # checking from i th value to n value minimum perfect squares required for j in range(len(arr)): # check if index doesn't goes out of bound if (i + arr[j] <= n): dp[i] = min(dp[i], dp[i + arr[j]]); # from current to go to min step one i we need to take one step dp[i] += 1; return dp[0]; # Driver code if __name__ == '__main__': print(numSquares(12)); # This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to count minimum
// squares that sum to n
static int numSquares(int n)
{
// Making the array of perfect squares less than or equal to n
List <int> arr = new List<int>();
int k = 1;
while(k * k <= n){
arr.Add(k * k);
k++;
}
// A dp array which will store minimum number of perfect squares
// required to make n from i at i th index
int []dp = new int[n + 1];
for(int i = 0; i < n + 1; i++)
dp[i] = int.MaxValue;
dp[n] = 0;
for(int i = n - 1; i >= 0; i--)
{
// checking from i th value to n value minimum perfect squares required
for(int j = 0; j < arr.Count; j++)
{
// check if index doesn't goes out of bound
if(i + arr[j] <= n)
{
dp[i] = Math.Min(dp[i], dp[i+arr[j]]);
}
}
// from current to go to min step one i we need to take one step
dp[i]++;
}
return dp[0];
}
// Driver code
public static void Main(String[] args)
{
Console.Write(numSquares(12));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program for the above approach
// Function to count minimum
// squares that sum to n
function numSquares(n) {
// Making the array of perfect squares less than or equal to n
var arr = new Array();
var k = 1;
while (k * k <= n) {
arr.push(k * k);
k++;
}
// A dp array which will store minimum number of perfect squares
// required to make n from i at i th index
var dp = Array(n + 1).fill(Number.MAX_VALUE);
dp[n] = 0;
for (i = n - 1; i >= 0; i--) {
// checking from i th value to n value minimum perfect squares required
for (j = 0; j < arr.length; j++) {
// check if index doesn't goes out of bound
if (i + arr[j] <= n) {
dp[i] = Math.min(dp[i], dp[i + arr[j]]);
}
}
// from current to go to min step one i we need to take one step
dp[i]++;
}
return dp[0];
}
// Driver code
document.write(numSquares(12));
// This code is contributed by umadevi9616
</script>
Producción
3
La complejidad de tiempo del problema anterior es O(n)*sqrt(n) ya que la array se creará en sqrt(n) y los bucles para llenar la array dp tomarán n*sqrt(n) como máximo. El tamaño de la array dp será n, por lo que la complejidad espacial de este enfoque es O (n).
Otro enfoque: (usando las matemáticas)
La solución se basa en el teorema de los cuatro cuadrados de Lagrange.
Según el teorema, puede haber como máximo 4 soluciones al problema, es decir, 1, 2, 3, 4
Caso 1:
Respuesta = 1 => Esto puede suceder si el número es un número cuadrado.
n = {a 2 : a ∈ W}
Ejemplo : 1, 4, 9, etc.
Caso 2:
Respuesta = 2 => Esto es posible si el número es la suma de 2 números cuadrados.
n = {a 2 + b 2 : a, b ∈ W}
Ejemplo : 2, 5, 18, etc.
Caso 3:
Respuesta = 3 => Esto puede suceder si el número no es de la forma 4 k (8m + 7).
Para más información sobre esto: https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem
n = {a 2 + b 2 + c 2 : a, b, c ∈ W} ⟷ n ≢ {4k(8m + 7) : k, m ∈ W }
Ejemplo: 6, 11, 12 etc.
Caso 4:
Respuesta = 4 => Esto puede suceder si el número es de la forma 4 k (8m + 7).
n = {a 2 + b 2 + c 2 + d 2 : a, b, c, d ∈ W} ⟷ n ≡ {4k(8m + 7) : k, m ∈ W }
Ejemplo: 7, 15, 23 etc. .
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// returns true if the input number x is a square number,
// else returns false
bool isSquare(int x)
{
int sqRoot = sqrt(x);
return (sqRoot * sqRoot == x);
}
// Function to count minimum squares that sum to n
int cntSquares(int n)
{
// ans = 1 if the number is a perfect square
if (isSquare(n)) {
return 1;
}
// ans = 2:
// we check for each i if n - (i * i) is a perfect
// square
for (int i = 1; i <= (int)sqrt(n)+1; i++) {
if (isSquare(n - (i * i))) {
return 2;
}
}
// ans = 4
// possible if the number is representable in the form
// 4^a (8*b + 7).
while (n % 4 == 0) {
n >>= 2;
}
if (n % 8 == 7) {
return 4;
}
// since all the other cases have been evaluated, the
// answer can only then be 3 if the program reaches here
return 3;
}
// Driver Code
int main()
{
cout << cntSquares(12) << endl;
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG{
// returns true if the input number x is a square number,
// else returns false
static boolean isSquare(int x)
{
int sqRoot = (int)Math.sqrt(x);
return (sqRoot * sqRoot == x);
}
// Function to count minimum squares that sum to n
static int cntSquares(int n)
{
// ans = 1 if the number is a perfect square
if (isSquare(n)) {
return 1;
}
// ans = 2:
// we check for each i if n - (i * i) is a perfect
// square
for (int i = 1; i <= (int)Math.sqrt(n)+1; i++) {
if (isSquare(n - (i * i))) {
return 2;
}
}
// ans = 4
// possible if the number is representable in the form
// 4^a (8*b + 7).
while (n % 4 == 0) {
n >>= 2;
}
if (n % 8 == 7) {
return 4;
}
// since all the other cases have been evaluated, the
// answer can only then be 3 if the program reaches here
return 3;
}
// Driver Code
public static void main(String[] args)
{
System.out.print(cntSquares(12) +"\n");
}
}
// This code is contributed by umadevi9616
Python3
# Python code for the above approach import math # returns True if the input number x is a square number, # else returns False def isSquare(x): sqRoot = int(math.sqrt(x)); return (sqRoot * sqRoot == x); # Function to count minimum squares that sum to n def cntSquares(n): # ans = 1 if the number is a perfect square if (isSquare(n)): return 1; # ans = 2: # we check for each i if n - (i * i) is a perfect # square for i in range(1, int(math.sqrt(n))+1): if (isSquare(n - (i * i))): return 2; # ans = 4 # possible if the number is representable in the form # 4^a (8*b + 7). while (n % 4 == 0): n >>= 2; if (n % 8 == 7): return 4; # since all the other cases have been evaluated, the # answer can only then be 3 if the program reaches here return 3; # Driver Code if __name__ == '__main__': print(cntSquares(12) , ""); # This code is contributed by gauravrajput1
C#
// C# code for the above approach
using System;
public class GFG{
// returns true if the input number x is a square number,
// else returns false
static bool isSquare(int x)
{
int sqRoot = (int)Math.Sqrt(x);
return (sqRoot * sqRoot == x);
}
// Function to count minimum squares that sum to n
static int cntSquares(int n)
{
// ans = 1 if the number is a perfect square
if (isSquare(n)) {
return 1;
}
// ans = 2:
// we check for each i if n - (i * i) is a perfect
// square
for (int i = 1; i <= (int)Math.Sqrt(n)+1; i++) {
if (isSquare(n - (i * i))) {
return 2;
}
}
// ans = 4
// possible if the number is representable in the form
// 4^a (8*b + 7).
while (n % 4 == 0) {
n >>= 2;
}
if (n % 8 == 7) {
return 4;
}
// since all the other cases have been evaluated, the
// answer can only then be 3 if the program reaches here
return 3;
}
// Driver Code
public static void Main(String[] args)
{
Console.Write(cntSquares(12) +"\n");
}
}
// This code contributed by umadevi9616
Javascript
<script>
// javascript code for the above approach
// returns true if the input number x is a square number,
// else returns false
function isSquare(x) {
var sqRoot = parseInt( Math.sqrt(x));
return (sqRoot * sqRoot == x);
}
// Function to count minimum squares that sum to n
function cntSquares(n)
{
// ans = 1 if the number is a perfect square
if (isSquare(n)) {
return 1;
}
// ans = 2:
// we check for each i if n - (i * i) is a perfect
// square
for (var i = 1; i <= parseInt( Math.sqrt(n))+1; i++) {
if (isSquare(n - (i * i))) {
return 2;
}
}
// ans = 4
// possible if the number is representable in the form
// 4^a (8*b + 7).
while (n % 4 == 0) {
n >>= 2;
}
if (n % 8 == 7) {
return 4;
}
// since all the other cases have been evaluated, the
// answer can only then be 3 if the program reaches here
return 3;
}
// Driver Code
document.write(cntSquares(12) + "\n");
// This code is contributed by umadevi9616
</script>
Producción
3
Complejidad de tiempo: O(sqrt(n))
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA