Toggle bulb’s switches

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in company
IBM

Problem statement

There are ‘N’ bulbs in a room, and all are initially switched off. You have to go through the bulbs ‘N’ times and toggle the bulb’s switches (if initially switch on, then switch off and vice-versa). It is also given that in the ‘ i-th ’ go., you can toggle only those bulbs that are multiples of ‘i‘.

For Example - In the 2nd go, you can toggle bulbs - 2nd,4th,6th,8th….

You have to find the bulbs that will be switched on at the end of the ‘N'th go.

Example: 
If there are 4 bulbs in the room, all initially switched off [ 0, 0, 0, 0 ], we will go through the bulbs ‘4’ times.

In 1st go, All the bulbs will be switched on. [ 1,1, 1, 1 ]
In the 2nd go, 2nd, 4th bulb will be toggled -> [ 1, 0, 1, 0 ]
In the 3rd go, the 3rd bulb will be toggled. -> [ 1, 0. 0, 0 ]
In the 4th go, 4th bulb will be toggled -> [ 1, 0, 0, 1 ].

After ‘N'th go, i.e., 4th go 1st and 4th bulb is switched on. So you have to return 1 and 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains ‘ N ‘, denoting the number of bulbs in the room.
Output Format: 
For each test case, you need to return the space-separated integers denoting the bulbs’ position that will be switched on.

Print the output of each test case in a separated line.
Constraints 
1 <= T <= 10
1 <= N <= 10^5

Time limit: 1 sec
Sample Input 1
2
5
3
Sample Output 1
1 4
1
Explanation For Sample Output 1:
In test case 1, There are 5  bulbs in the room, and we have to go through the bulbs ‘5’ times.
Let ‘0’ represent  ‘off’ state, and ‘1’ represent ‘on’ state of the bulb.
Initially all the bulbs will be switched off [ 0, 0, 0, 0, 0 ]
In the first go all the bulbs will get switched on.[ 1, 1,1,1,1 ]
In the second go 2nd or 4th bulb will be toggled -> [ 1, 0, 1, 0, 1 ].
In the third go 3rd will be toggled and switched off -> [ 1, 0, 0, 0, 1 ]
In the fourth go 4th will be toggled  -> [ 1, 0, 0, 1, 1 ]
In the fifth go 5th will be toggled  -> [ 1, 0, 0, 1, 0 ].

As the 1st and 4th bulbs are switched on, the answer will be 1, 4.

In test case 2, There are 3 bulbs and in 3 rounds switches of bulb will be:
1st -> [ 1, 1, 1 ]
2nd -> [ 1, 0, 1 ]
3rd -> [ 1, 0, 0 ]

So the answer will be 1.
Sample Input 2:
2
1
2
Sample Output 2:
1
1
Explanation For Sample Output 2:
In test case 1, There is 1 bulb in the room, and we have to go through the bulbs ‘1’  times.
Let ‘0’ represent  ‘off’ state, and ‘1’ represent ‘on’ state of the bulb.
Initially all the bulbs will be switched off [ 0 ].
In the first go all the bulbs will get switched on.[ 1]

As the 1st bulb is switched on, the answer will be 1.

In test case 2, There are 2 bulbs and in 2 rounds switches of bulb will be:
1st -> [ 1, 1 ]
2nd -> [ 1, 0 ]

So the answer will be 1.
Hint

Try to toggle the bulb for every go for each of the number form 1 to ‘N’.

Approaches (2)
Brute Force Approach

The simple idea is that we will take an array ‘STATE’ (with all initial values 0), where ‘STATE[ i ]’ = 0 denotes the ‘off’ state of ‘ i-th ‘ bulb and ‘STATE[ i ]’ =1 denotes the ‘on’ state of the ‘ i-th ‘ bulb. We will run a loop of ‘ i ‘ from 1 to ‘N’ and in each iteration, we will toggle all the multiples of ‘i‘. After ‘ N-th ’ go, all the indexes where the value of the ‘STATE’ array is 1 will be our required answer.

 

The steps are as follows:

 

  • Initialize an array ‘STATE’ of size 'N' + 1 and an array ‘RES’ to store the result.
  • Run a loop ‘i’: 1 to ‘N’
    • Run a loop ‘j’: ‘i’ to ‘N’ to visit all multiples of ‘i‘ and in each iteration increment j by ‘i‘.
      • If ‘STATE[ j ]’ is ‘ 0 ‘, update ‘STATE[ j ]’ = 1 and vice-versa.
  • Iterate through the ‘STATE’ array - ‘i’: 1 to ‘N’:
    • If 'STATE[ i ]' = 1, push ‘i‘ to ‘RES’.
  • Return ‘RES’.
Time Complexity

O(N ^ 2), Where ‘N’ is the number of bulbs in the room.

 

Since we are iterating through all the bulbs for every go for each of the ‘N’ bulb. So the overall time complexity is O(N ^ 2).

Space Complexity

O( N ), Where ‘N’ is the number of bulbs in the room.

 

Since we have used an extra array of size ‘N‘ which makes the space complexity O( N ).

Code Solution
(100% EXP penalty)
Toggle bulb’s switches
Full screen
Console