Today we continue to review a coding problem.
The problem statement:
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On 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, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
for example if there are five bulbs:
Initially  [ 0, 0, 0, 0, 0]
Round 1 [ 1, 1, 1, 1, 1]
Round 2 [ 1, 0, 1, 0, 1]
Round 3 [ 1, 0, 0, 0, 1]

Round 4 [ 1, 0, 0, 1, 1]

Round 5 [ 1, 0, 0, 1, 0]

The solution:

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

The reasoning:
A bulb ends up on only if it is switched an odd number of times.
bulbs 1 to n has a bulb i that is switched in round  d only if d divides i.
bulb i is in a switched on state only if it has an odd number of divisors.
but divisors come in pairs except for squares and pairs returns to original state
so only squares leave a toggled state and the initial state is all off
therefore we count only the squares uptil and inclusive of the number
Thus the answer is Math.sqrt(n)

courtesy: Stefan Pochmann

We implement square root with gradient method. If y ^ 2 = x then y = x / y
And we iteratively improve the approximation
Double SqRt (int n)
{
Double g = n/2;
Double y = n/g;
While(abs (y-g) > 0.001)
{
   g = (g + n/g) /2;
   y = n / g;
}
Return y;
}