Minimum number of squares whose sum equals to given number N | set 2 | Function for finding minimum square numbers ; arr [ i ] of array arr store minimum count of square number to get i ; sqrNum [ i ] store last square number to get i ; Find minimum count of square number for all value 1 to n ; In worst case it will be arr [ i - 1 ] + 1 we use all combination of a [ i - 1 ] and add 1 ; Check for all square number less or equal to i ; If it gives less count then update it ; v stores optimum square number whose sum give N ; Driver code ; Calling function ; Printing vector
def minSqrNum ( n ) : NEW_LINE INDENT arr = [ 0 ] * ( n + 1 ) NEW_LINE sqrNum = [ 0 ] * ( n + 1 ) NEW_LINE v = [ ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT arr [ i ] = arr [ i - 1 ] + 1 NEW_LINE sqrNum [ i ] = 1 NEW_LINE k = 1 ; NEW_LINE while ( k * k <= i ) : NEW_LINE INDENT if ( arr [ i ] > arr [ i - k * k ] + 1 ) : NEW_LINE INDENT arr [ i ] = arr [ i - k * k ] + 1 NEW_LINE sqrNum [ i ] = k * k NEW_LINE DEDENT k += 1 NEW_LINE DEDENT DEDENT while ( n > 0 ) : NEW_LINE INDENT v . append ( sqrNum [ n ] ) NEW_LINE n -= sqrNum [ n ] ; NEW_LINE DEDENT return v NEW_LINE DEDENT n = 10 NEW_LINE v = minSqrNum ( n ) NEW_LINE for i in range ( len ( v ) ) : NEW_LINE INDENT print ( v [ i ] , end = " " ) NEW_LINE if ( i < len ( v ) - 1 ) : NEW_LINE INDENT print ( " ▁ + ▁ " , end = " " ) NEW_LINE DEDENT DEDENT