Check if the door is open or closed

Easy

0/40

Average time to solve is 10m

16 upvotes

Asked in company

Problem statement

There are ‘N’ doors and ‘N’ people in a house. Each person and door has a unique ID ranging from 1 to ‘N’. A person can change the status of the door i.e, if the door is open then a person can close the door and vice versa. Initially, all the doors are closed and each person wants to change the status of all doors whose ID is a multiple of the ID of the person. You need to find out the final status of all the doors.

The answer should be given in a form of a binary string where ‘0’ represents the closed door and ‘1’ represents the open door. For example, the status “close open close” will form a binary string “010”.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The only line of each test case contains a single positive integer ‘N’ denoting the number of doors and persons.

Output Format:

The only line of output of each test case should contain a binary string representing the final status of doors.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this in O(N) time and using constant extra space. The output string does not count as extra space.

Constraints:

1 <= T <= 100
1 <= N <= 10^4  

Time Limit: 1 sec

Sample Input 1:

2
2
4

Sample Output 1:

10
1001

Explanation for sample input 1:

Test case 1:
Initially, all the doors are closed -> 00
The first person has an ID 1 so it will change the status of doors 1(1 * 1) and 2(1 * 2) -> 11
The second person has an ID 2 so it will change the status of door 2 (2 * 1)-> 10

Test case 2:
Initially, all the doors are closed -> 0000
The first person has an ID 1 so it will change the status of door 1, 2, 3 and 4 -> 1111
The second person has an ID 2 so it will change the status of door  2 and 4 -> 1010
The third person has an ID 3 so it will change the status of door 3-> 1000
The fourth person has an ID 4 so it will change the status of door 4 -> 1001

Sample Input 2:

2
6
8

Sample Output 2:

100100
10010000

Hint 1

Hint 2

Find all multiples of every person's ID.

Approaches (2)

Approach 1

Approach 2

Maths

We will create a boolean array ‘STATUS[]’. The STATUS[i] will represent the current status of the ith door. Initially, all the elements in the status array are false representing that all the doors are closed.
We traverse on each multiple of every number from 1 to N. If we are traversing on the multiple of ith number then we will flip (change true to false and vice versa) the value of STATUS[j] of ‘j’ is the multiple of ‘i’.
Finally, we build our string by traversing the STATUS[] array if STATUS[i] is true representing an open door we will append ‘1’ in our string else we append ‘0’.

Time Complexity

O(N * log(N)), where ‘N’ is the number of doors.

We are traversing on multiples of ‘N’ numbers from 1 to N.

The number ‘K’ will have N/K multiples from 1 to N.

So N/1 + N/2 + N/3 + N/4 + ….. + N/N = N*log(N)

Space Complexity

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

We are using an extra array of size ‘N’.

(100% EXP penalty)

Check if the door is open or closed

Console