Minimum number of squares whose sum equals to given number n | Python3 program for the above approach ; Function to count minimum squares that sum to n ; Creating visited vector of size n + 1 ; Queue of pair to store node and number of steps ; Initially ans variable is initialized with inf ; Push starting node with 0 0 indicate current number of step to reach n ; Mark starting node visited ; If node reaches its destination 0 update it with answer ; Loop for all possible path from 1 to i * i <= current node ( p . first ) ; 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 ) ; Check if it is valid and not visited yet ; Mark visited ; Push it it Queue ; Return ans to calling function ; Driver code
import sys NEW_LINE def numSquares ( n ) : NEW_LINE INDENT visited = [ 0 ] * ( n + 1 ) NEW_LINE q = [ ] NEW_LINE ans = sys . maxsize NEW_LINE q . append ( [ n , 0 ] ) NEW_LINE visited [ n ] = 1 NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT p = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE if ( p [ 0 ] == 0 ) : NEW_LINE INDENT ans = min ( ans , p [ 1 ] ) NEW_LINE DEDENT i = 1 NEW_LINE while i * i <= p [ 0 ] : NEW_LINE INDENT path = p [ 0 ] - i * i NEW_LINE if path >= 0 and ( visited [ path ] == 0 or path == 0 ) : NEW_LINE INDENT visited [ path ] = 1 NEW_LINE q . append ( [ path , p [ 1 ] + 1 ] ) NEW_LINE DEDENT i += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT print ( numSquares ( 12 ) ) NEW_LINE