Day 34 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/get-minimum-squares0538/1

Get Minimum Squares

D*ifficulty: Medium Accuracy: 45.22%*

Given a positive integer n, find the minimum number of perfect squares (square of an integer) that sum up to n.
Note: Every positive integer can be expressed as a sum of square numbers since 1 is a perfect square, and any number can be represented as 1*1 + 1*1 + 1*1 + ....
Examples:
Input: n = 100
Output: 1
Explanation: 10 * 10 = 100
Input: n = 6
Output: 3
Explanation = 1 * 1 + 1 * 1 + 2 * 2 = 6
Constraints:
1 ≤ n ≤ 104

Solution:
class Solution:
def minSquares(self, n):
dp = [0] + [float('inf')] * n
for i in range(1, n + 1):
j = 1
while j * j <= i:
dp[i] = min(dp[i], 1 + dp[i - j * j])
j += 1
return dp[n]