Problem Description

Question

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12

Output: 3

Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13

Output: 2

Explanation: 13 = 4 + 9.

Constraints:

1 <= n <= 10⁴

Solve it on LeetCode

Approaches

1. Brute Force using Recursion

Intuition:

The simplest way to solve the problem is by trying all combinations. For a given number n, see if you can subtract a perfect square and solve the rest of the problem for n - perfect_square recursively.

Steps:

Recursive function will be called reducing n by i*i, where i goes from 1 to sqrt(n).
Base case: If n is 0, return 0 as we do not need any squares to sum up to 0.
Return the minimum number of squares necessary.

Code:

Complexity Analysis

Time Complexity: O(n^(n/2)), since each branch of recursion can branch further into sqrt(n) branches.
Space Complexity: O(n), due to the recursion call stack.

2. Dynamic Programming

Intuition:

We can improve upon the recursive approach by storing results of subproblems (memoization). Use an array where dp[i] keeps track of the least number of perfect squares that sum up to i.

Steps:

Initialize an array dp of size n + 1 where dp[0] = 0.
Iterate over each number up to n and compute dp[i] by adding a perfect square j*j.
For each i, dp[i] equals the min of dp[i] and dp[i - j*j] + 1.

Code:

Complexity Analysis

Time Complexity: O(n * sqrt(n)), as you go through each number and compute the squares up to sqrt(n).
Space Complexity: O(n), additional space for the dp array.

3. Mathematical Approach using Lagrange's Four Square Theorem

Intuition:

Lagrange's Four Square Theorem states that any natural number is the sum of four integer squares at most. Using some mathematical deductions, especially checking for perfect squares can make the solution optimal.

Steps:

Check if n is a perfect square.
Applying a few checks based on the property of modulo 4 and perfect number subtraction.

Code:

Complexity Analysis

Time Complexity: O(sqrt(n)), due to verification of perfect squares.
Space Complexity: O(1), using only constant space.

Perfect Squares

Ashish Pratap Singh

Problem Description

Example 1:

Example 2:

Constraints:

Solve it on LeetCode

Approaches

1. Brute Force using Recursion

Intuition:

Steps:

Code:

2. Dynamic Programming

Intuition:

Steps:

Code:

3. Mathematical Approach using Lagrange's Four Square Theorem

Intuition:

Steps:

Code:

Get Premium