Minimum number of squares whose sum equals to given number N | set 2 | Function for finding minimum square numbers ; A [ i ] of array arr store minimum count of square number to get i ; sqrNum [ i ] store last square number to get i ; Initialize ; 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 ; Vector v stores optimum square number whose sum give N ; Driver code ; Calling function ; Printing vector
function minSqrNum ( n ) { var arr = Array ( n + 1 ) , k ; var sqrNum = Array ( n + 1 ) ; var v = [ ] ; arr [ 0 ] = 0 ; sqrNum [ 0 ] = 0 ; for ( var i = 1 ; i <= n ; i ++ ) { arr [ i ] = arr [ i - 1 ] + 1 ; sqrNum [ i ] = 1 ; k = 1 ; while ( k * k <= i ) { if ( arr [ i ] > arr [ i - k * k ] + 1 ) { arr [ i ] = arr [ i - k * k ] + 1 ; sqrNum [ i ] = k * k ; } k ++ ; } } while ( n > 0 ) { v . push ( sqrNum [ n ] ) ; n -= sqrNum [ n ] ; } return v ; } var n = 10 ; var v = [ ] ; v = minSqrNum ( n ) ; for ( var i = 0 ; i < v . length ; i ++ ) { document . write ( v [ i ] ) ; if ( i + 1 != v . length ) document . write ( " " ) ; }