Last Updated: 29 Dec, 2020
Check if the door is open or closed
Easy
Asked in company
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”.
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
Approaches
- 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’.
- If you observe that we are flipping the status of the door which depends upon the parity of the total number of factors of each door ID.
- If the door ID has the odd number of factors then the final status will be Open and if it has an even number of factors then the final status will be closed.
- Now how to calculate the total number of factors? The number of factors is odd if and only if the number is a perfect square.
- Proof: As we know the factors comes in pair that is If ‘i’ is the factor if ‘N’ then ‘N/i’ will also be a factor ‘N’ hence we can write i * (N/i) = N. As we see factors come in pairs so there will be an even number of factors.
- But what if i = N/i? then, in this case, we will consider only one factor instead of a pair of two. So the count of the total number of factors become odd and we can write the above equation as i * i = N. Thus it is seen that N = i^2 so N will have odd factors when it is a perfect square.
- So we just need to check if the current ID is a perfect square or not. If it is a perfect square then we will append ‘1’ in our string else we append ‘0’.