@@ -0,0 +1,1323 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On%0A * the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round,%0A * you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n%0A * rounds.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * Given n = 3.%0A * %3Cp%3E%0A * At first, the three bulbs are %5Boff, off, off%5D.%0A * After first round, the three bulbs are %5Bon, on, on%5D.%0A * After second round, the three bulbs are %5Bon, off, on%5D.%0A * After third round, the three bulbs are %5Bon, off, off%5D.%0A * %3Cp%3E%0A * So you should return 1, because there is only one bulb is on.%0A * %3Cp%3E%0A * Tags: Math, Brainteaser%0A */%0Apublic class BulbSwitch %7B%0A%0A    /**%0A     * Math.%0A     * A bulb ends up on if it's switched an odd number of times.%0A     * Bulb i is switched in round d iff d divides i.%0A     * So bulb i ends up on iff it has an odd number of divisors.%0A     * Divisors come in pairs, except when i is a square.%0A     * So just count the square numbers from 1 to n.%0A     * Possible square roots range from 1 to x, where x%5E2 %3C= n.%0A     * So x = int(sqrt(n)).%0A     */%0A    public int bulbSwitch(int n) %7B%0A        return (int) Math.sqrt(n);%0A    %7D%0A%0A%7D%0A

add Bulb Switch