LeetCode – Conmutador de bombillas (Java)

Hay n bombillas que inicialmente están apagadas. Primero enciende todas las bombillas. Luego, apaga cada segundo foco. En la tercera ronda, enciende cada tercer foco (se enciende si está apagado o se apaga si está encendido). Para la i-ésima ronda, cambia cada i bombilla. Para la enésima ronda, solo cambia la última bombilla. Encuentra cuántas bombillas están encendidas después de n rondas.

Análisis

Usando algunos ejemplos, podemos averiguar la cantidad de interruptores para cada bombilla:

1 -> 1 (1)
2 -> 2 (1 2)
3 -> 2 (1 3)
4 -> 3 (1 2 4)
5 -> 2 (1 5)
6 -> 4 (1 2 3 6)
7 -> 2 (1 7)
8 -> 4 (1 2 4 8)
9 -> 3 (1 3 9)

Entonces, solo (i * i) el elemento tiene un número impar de interruptores y están encendidos. El problema ahora es obtener todos los números cuadrados.

Solución Java 1: ingenuo

public int bulbSwitch(int n) {
    int count=0;
    for(int i=1; i<=n; i++){
        int numSwitch = helper(i);
        if(numSwitch%2 ==1)
            count++;
    }
 
    return count;
}
 
public int helper(int n){
    int count=0;
    for(int i=1; i<=n; i++){
        if(n%i==0)
            count++;
    }
    return count;
}

Solución Java 2: simplificada

public int bulbSwitch(int n) {
    return (int)Math.sqrt(n);
}