Minimum number of squares whose sum equals to a given number N | Set | C ++ program for the above approach ; Function that returns true if N is a perfect square ; Function that returns true check if N is sum of three squares ; Factor out the powers of 4 ; N is NOT of the form 4 ^ a * ( 8 b + 7 ) ; Function that finds the minimum number of square whose sum is N ; If N is perfect square ; If N is sum of 2 perfect squares ; If N is sum of 3 perfect squares ; Otherwise , N is the sum of 4 perfect squares ; Driver code ; Given number ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool isPerfectSquare ( int N ) { int floorSqrt = sqrt ( N ) ; return ( N == floorSqrt * floorSqrt ) ; } bool legendreFunction ( int N ) { while ( N % 4 == 0 ) N /= 4 ; if ( N % 8 != 7 ) return true ; else return false ; } int minSquares ( int N ) { if ( isPerfectSquare ( N ) ) return 1 ; for ( int i = 1 ; i * i < N ; i ++ ) { if ( isPerfectSquare ( N - i * i ) ) return 2 ; } if ( legendreFunction ( N ) ) return 3 ; return 4 ; } int main ( ) { int N = 123 ; cout << minSquares ( N ) ; return 0 ; }