Minimum number of squares whose sum equals to given number n | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int numSquares ( int n ) { vector < int > visited ( n + 1 , 0 ) ; queue < pair < int , int > > q ; int ans = INT_MAX ; q . push ( { n , 0 } ) ; visited [ n ] = 1 ; while ( ! q . empty ( ) ) { pair < int , int > p ; p = q . front ( ) ; q . pop ( ) ; if ( p . first == 0 ) ans = min ( ans , p . second ) ; for ( int i = 1 ; i * i <= p . first ; i ++ ) { int path = ( p . first - ( i * i ) ) ; if ( path >= 0 && ( ! visited [ path ] path == 0 ) ) { visited [ path ] = 1 ; q . push ( { path , p . second + 1 } ) ; } } } return ans ; } int main ( ) { cout << numSquares ( 12 ) ; return 0 ; }