Last Updated: 27 Mar, 2021

Toggle bulb’s switches

Easy

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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’.

Solve now

02 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 numbers, 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.

The steps are as follows:

Take a variable ‘NUM’ and initialize it to 1.
Take a 1-D array ‘RES’ to store the result.
Run a loop until the square of ‘NUM’ < ‘N’:
- Push square of ‘NUM’ to ‘RES’.
- Increment ‘NUM’.
Return ‘RES’.

Solve now