Minimum number of squares whose sum equals to given number N | set 2 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > minSqrNum ( int n ) { int arr [ n + 1 ] , k ; int sqrNum [ n + 1 ] ; vector < int > v ; 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 . push_back ( sqrNum [ n ] ) ; n -= sqrNum [ n ] ; } return v ; } int main ( ) { int n = 10 ; vector < int > v ; v = minSqrNum ( n ) ; for ( auto i = v . begin ( ) ; i != v . end ( ) ; i ++ ) { cout << * i ; if ( i + 1 != v . end ( ) ) cout << " ▁ + ▁ " ; } return 0 ; }