Minimum number of squares whose sum equals to given number N | set 2 | Java program to represent N as the sum of minimum square numbers . ; 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
import java . util . * ; class GFG { static Vector < Integer > minSqrNum ( int n ) { int [ ] arr = new int [ n + 1 ] ; int k = 0 ; int [ ] sqrNum = new int [ n + 1 ] ; Vector < Integer > v = new Vector < > ( ) ; arr [ 0 ] = 0 ; sqrNum [ 0 ] = 0 ; for ( int 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 . add ( sqrNum [ n ] ) ; n -= sqrNum [ n ] ; } return v ; } public static void main ( String [ ] args ) { int n = 10 ; Vector < Integer > v ; v = minSqrNum ( n ) ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { System . out . print ( v . elementAt ( i ) ) ; if ( i + 1 != v . size ( ) ) System . out . print ( " ▁ + ▁ " ) ; } } }