Ninja and the bulbs

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in companies
UberAmazonGoogle inc

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1
2
4
9
Sample output 1:
2
3
Explanation
Test case 1:

Here N = 4

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.

Test case 2:

Here N = 10.
In the first round, all bulbs are on.

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

In the third round bulb, 3 and 9 are turned off, and 6 is turned on.

In the fourth round, bulbs 4 and8 are turned on.

In the fifth round, bulbs 5 is turned off.

In the sixth round, bulb 6 is turned off.

In the seventh round, bulbs 7 is turned off.

In the eighth round, bulbs 8 is turned off.

In the ninth round, bulbs 9 is turned on.

So, in the end, bulbs 1, 4, and 9 are on. 
So the number of good bulbs is 3.
Sample Input 2:
2 
16
15
Sample Output 2:
4
3
Hint

Directly follow the Ninjas method.

Approaches (3)
Brute Force

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'.
Time Complexity

O(N^2), where ‘N’ is the number of bulbs.

 

For every round, we are traversing the whole array of bulbs. And we have ‘N’ bulbs so that the complexity will be N^2.

Space Complexity

O(N), where ‘N’ is the number of bulbs.

 

We are storing each bulbs’ status in a boolean array, and we have ‘N’ bulbs, so the space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja and the bulbs
Full screen
Console