package algorithm

import (
	llq "github.com/emirpasic/gods/queues/linkedlistqueue"
	"github.com/emirpasic/gods/sets/hashset"
)

// Problem Definition: https://leetcode.cn/problems/perfect-squares/

func numSquares1(n int) int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = i
		for j := 1; j*j <= i; j++ {
			dp[i] = min(dp[i], dp[i-j*j]+1)
		}
	}
	return dp[n]
}

func numSquares2(n int) int {
	que := llq.New()
	visited := hashset.New()
	que.Enqueue(0)
	visited.Add(0)
	level := 0

	for !que.Empty() {
		ll := que.Size()
		level++

		for i := 0; i < ll; i++ {
			digit, _ := que.Dequeue()
			for j := 1; j*j <= n; j++ {
				nodeValue := digit.(int) + j*j
				if nodeValue == n {
					return level
				}
				if nodeValue > n {
					break
				}
				if !visited.Contains(nodeValue) {
					que.Enqueue(nodeValue)
					visited.Add(nodeValue)
				}
			}
		}
	}

	return level
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}