Coding Problem 7

Este problema fue preguntado por Facebook en una entrevista.


Dado un entero positivo n, encuentra el número más pequeño de enteros elevados al cuadrado cuya suma sea n.


Por ejemplo, dado n = 13, devolvería 2, debido a que 13 = 3^2 + 2^2 = 9 + 4

Dado n = 27, devuelve 3 debido a que 27 = 3^2 + 3^2 + 3^2 = 9 + 9 + 9


Solución:


Empezamos como siempre con unos sencillos tests para nuestro código.


public class ProblemTest {
    
    @Test
    public void shouldReturnMinimumSquares() {
        assertEquals(1, Problem.getMinumumSquares(1));
        assertEquals(2, Problem.getMinumumSquares(2));
        assertEquals(2, Problem.getMinumumSquares(13));
    }

    @Test
    public void shouldReturnMinimumSquaresComplex() {
        assertEquals(3, Problem.getMinumumSquares(27));
        assertEquals(3, Problem.getMinumumSquares(21));
    }
}

Como vemos, existe un caso particular que es el 1, el 0 no lo tratamos porque debe ser positivo.


El código que se me ha ocurrido a la primera, para pasar los tests, porque recordemos que esto es algo importante de TDD, primero tests, y luego el código más sencillo para pasar los tests, ya luego refactorizamos, porque he visto a mucha gente intentando hacer un código perfecto a la primera y no es así.


Código productivo:

    public static int getMinumumSquares(int number) {
        if(number == 1) return 1;

        int maxSquare = number / 2;
        int count = 0;
        int result = 0;

        for (int i = maxSquare; i > 0; i--) {
                result = (int) Math.pow(i, 2) + result;
                if (result < number) {
                    count++;
                    i = i + 1;
                }else if(result == number){
                    count++;
                    i = 0;
                }else{
                    result -= (int) Math.pow(i, 2);
                }
        }

        return count;
    }
}

Como veis es un código un poco complejo y no dice mucho, lo que hago es comprobar los números al cuadrado desde la mitad del que le paso hacia abajo, y si es menor, pruebo a sumarlo de nuevo hasta que sea mayor y pruebe con el siguiente, en caso de ser mayor directamente no sumo ni cuento. Vamos a refactorizar el código un poco:


Bueno, no he podido mejorarlo mucho, he intentado darle otro enfoque, pero no se me ha ocurrido nada más sencillo a priori, lo que he hecho ha sido mejorar el rendimiento y el nombrado de variables, si encontrais algo más optimo, compartidlo, yo miraré en Internet para aprender, os dejo con el código final:



public class Problem {

    public static int getMinumumSquares(int number) {
        if (number == 1) return 1;

        int maxSquare = (int) Math.sqrt(number);
        int numberOfSquares = 0;
        double result = 0;

        for (int numberToSquare = maxSquare; numberToSquare > 0; numberToSquare--) {
            result += Math.pow(numberToSquare, 2);

            if (result < number) {
                numberOfSquares++;
                numberToSquare++;
            } else if (result == number) {
                numberOfSquares++;
                numberToSquare = 0;
            } else {
                result -= Math.pow(numberToSquare, 2);
            }
        }

        return numberOfSquares;
    }
}

122 vistas

©2020 por Juanma Perez.