Last Updated: 6 Apr, 2021

Ninja and the bulbs

Moderate

Asked in companies

Solve now

Problem statement

Ninja owns an electronic shop. In the shop, Ninja has 'N' bulbs. To sell these bulbs, Ninja has to check if they are of good quality. To check bulbs, Ninja uses a unique technique.

In this technique, in the first round he, turn on all the bulbs, then in the second round, he turns off every second bulb then in the third round, he chooses every third bulb and turns off it is on, or turn on if it is off and so no. He repeats this process 'N' times.

The number of bulbs that are on after the end of 'N' rounds are of good quality. Your task is to help Ninja in finding the number of good bulbs.

Example

Let 'N' = 4

Then in the first round, all bulbs are on.

In the second round bulbs, 2 and 4 are turned off.

In the third round bulb, 3 is turned off.

In the fourth round bulb, 4 is turned on.

So at the end of 'N' (4) round, only the bulb 1 and 4 is on, so there are 2 good bulbs.

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

Each test case contains an integer 'N' representing the number of bulbs.

Output Format :

For every test case, return an integer denoting the number of good bulbs.

Note:

You don’t need to take input or print anything. This already has been taken care of. Just implement the function.

Constraints

1 <= T <= 10
1 <= N <= 10^9

Time limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

A brute force solution to this problem is to turn on and off the bulbs N time, then at last check the number of bulbs that are on.

Algorithm:

Take a boolean array of ‘BULBS’ of size N+1.
Itertate on ‘i’ from 1 to ‘N’
- Iterate on ‘j’ form ‘i’ to ‘N’ and each time increment ‘j’ as ‘j’ += ‘i’.
  - if(BULBS[j] == true) then make it false.
  - If (BULBS[j]==false) then make it true.
Intialise a variable ‘COUNT’ = 0.
Iterate on ‘i’ form 1 to ‘N’.
- if ( BULBS[i] == true) then increase the 'COUNT' by 1.
Return 'COUNT'.

Solve now

02 Approach

Approach:

In the ‘ i-th ‘ go, we will toggle all the bulbs that are multiples of ‘ i ‘.
Let’s say ‘ K ‘ be any multiple of ‘ i ‘, then it will be toggled in ‘ i-th’ go as well as in ‘ K/i - th’ go as k/i will also be a multiple of ‘K’.
So we can assume that the toggle effect in ‘ i-th ’ go can be canceled by a toggle in‘ K/i - th’ move.
In other words, we can say that there will be an even number of toggles for a switch. But this does not hold for perfect square numbers as for perfect square; there will always be odd numbers of toggles.
For Example, bulb number 20 will be toggled in 1st, 2nd, 4th, 5th, 10th, and 20th move.

But bulb number 16 will be toggled in 1st, 2nd, 4th, 8th, 16th move

We can say the bulbs with an even number of toggles will be switched off at the end, and bulbs with the odd number of toggles will be switched on. So all the bulbs having numbers that are perfect squares will be switched on at the end.
So we simply have to find the number of perfect squares till ‘N’.

Algorithm:

If ‘N’ == 1, then return ‘N’.
Initialize a variable int ‘i’ = 1 and ‘RES’ = 1.
Starting from 1 check all the numbers till ‘i*i’ is less than or equal to ‘N’.
while(‘RES’ <= ‘N’)
- Increase ‘i’ by 1/
- Increase ‘RES’ as ‘RES’ = ‘i*i’.
Return - value of (i - 1).

Solve now

03 Approach

We can use the method of binary search to find the square root of ‘N’.

Algorithm:

Take care of some base cases, ‘i’.ehen the given number is 0 or 1.
Create some variables, lower bound ‘l’ = 0, upper bound ‘r’ = ‘N’, where ‘N’ is the number of bulbs, ‘MID' and ‘ANS’ to store the answer.
Run a loop until ‘l’ <= ‘r’ , the search space vanishes
Check if the square of mid ('MID' = ('l' + ‘r’)/2 ) is less than or equal to ‘N’, If yes, then search for a larger value in the second half of search space, i.e., ‘l’ = ‘MID’ + 1, update ‘ANS’ = ‘MID’
Else if the square of mid is less than ‘N’, the then search for a smaller value in the first half of i.e.of search space, i.e ‘r’ = ‘MID’ – 1
We finally return ‘ANS’.

Solve now