Minimum number of squares whose sum equals to given number n | Java 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 java . util . * ; import java . awt . Point ; class GFG { public static int numSquares ( int n ) { int visited [ ] = new int [ n + 1 ] ; Queue < Point > q = new LinkedList < > ( ) ; int ans = Integer . MAX_VALUE ; q . add ( new Point ( n , 0 ) ) ; visited [ n ] = 1 ; while ( q . size ( ) != 0 ) { Point p = q . peek ( ) ; q . poll ( ) ; if ( p . x == 0 ) ans = Math . min ( ans , p . y ) ; for ( int i = 1 ; i * i <= p . x ; i ++ ) { int path = ( p . x - ( i * i ) ) ; if ( path >= 0 && ( visited [ path ] == 0 path == 0 ) ) { visited [ path ] = 1 ; q . add ( new Point ( path , p . y + 1 ) ) ; } } } return ans ; } public static void main ( String [ ] args ) { System . out . println ( numSquares ( 12 ) ) ; } }