Question

Find the minimum number of squares that sum of them equal to a given number in C++

Answer 1

#include <iostream>
#include <cmath>

bool isPerfectSquare(int n) {
    long double sqr = sqrt(n);
 
    return sqr == floor(sqr);
}
 
int findMinSquares(int n) {
    if (isPerfectSquare(n)) {
        return 1;
    }
 
    int result = n;
 
    for (int i = 1; i * i < n; i++) {
        result = std::min(result, 1 + findMinSquares(n - i*i));
    }
 
    return result;
}
 
int main()
{
    int n = 63; // 63 = 7*7(49) + 3*3(9) + 2*2(4) + 1*1(1) // 4 number of squares
    std::cout << "The minimum number of squares: " << findMinSquares(n) << "\n";
         
    n = 23; // 23 = 3*3(9) + 3*3(9) + 2*2(4) + 1*1(1) // 4 number of squares
    std::cout << "The minimum number of squares: " << findMinSquares(n) << "\n";
         
    n = 100; // 100 = 10*10(100) // 1 number of squares
    std::cout << "The minimum number of squares: " << findMinSquares(n) << "\n";
 
    return 0;
}



 
 
 
 
/*
run:
  
The minimum number of squares: 4
The minimum number of squares: 4
The minimum number of squares: 1
  
*/

 

70+ SQL courses for beginners and professionals