Question

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

Answer 1

public class MyClass {
    public static boolean isPerfectSquare(int n) {
        double sqr = Math.sqrt(n);
 
        return sqr == Math.floor(sqr);
    }
    public static int findMinSquares(int n)
    {
        if (isPerfectSquare(n)) {
            return 1;
        }
 
        int squares = n;

        for (int i = 1; i * i < n; i++) {
            squares = Integer.min(squares, 1 + findMinSquares(n - i * i));
        }
 
        return squares;
    }
 
    public static void main(String args[]) {
        int n = 63; // 63 = 7*7(49) + 3*3(9) + 2*2(4) + 1*1(1) // 4 number of squares
        System.out.println("The minimum number of squares: " + findMinSquares(n));
        
        n = 23; // 23 = 3*3(9) + 3*3(9) + 2*2(4) + 1*1(1) // 4 number of squares
        System.out.println("The minimum number of squares: " + findMinSquares(n));
        
        n = 100; // 100 = 10*10(100) // 1 number of squares
        System.out.println("The minimum number of squares: " + findMinSquares(n));

    } 
}




/*
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