Check if the door is open or closed - GeeksforGeeks
Given n doors and n persons. The doors are numbered 1 to n and persons are given id's numbered 1 to n. Each door can have only 2 status open and closed. Initially all the doors have status closed. Find the final status of all the doors if a person changes the current status of all the doors, i.e. if status open then change to status closed and vice versa, for which he is authorized. A person with id 'i' is authorized to change the status of door numbered 'j' if 'j' is a multiple of 'i'.
Note:
– A person has to change the current status of all the doors for which he is authorized exactly once.
– There can be a situation that before a person changes the status of the door, another person who is also authorized for the same door changes the status of the door.
Read full article from Check if the door is open or closed - GeeksforGeeks
Given n doors and n persons. The doors are numbered 1 to n and persons are given id's numbered 1 to n. Each door can have only 2 status open and closed. Initially all the doors have status closed. Find the final status of all the doors if a person changes the current status of all the doors, i.e. if status open then change to status closed and vice versa, for which he is authorized. A person with id 'i' is authorized to change the status of door numbered 'j' if 'j' is a multiple of 'i'.
Note:
– A person has to change the current status of all the doors for which he is authorized exactly once.
– There can be a situation that before a person changes the status of the door, another person who is also authorized for the same door changes the status of the door.
Approach: It is mathematical and logical approach. If we observe it properly, then we find that the final status of a door numbered i is open if ‘i’ has odd number of factors and status is closed if ‘i’ has even number of factors. It does not depend in which sequence the status of doors are changed. To find whether count of divisors of number is even or odd, we can see Check if count of divisors is even or odd post.
// Function to check whether 'n'
// has even number of factors or not
bool
hasEvenNumberOfFactors(
int
n)
{
int
root_n =
sqrt
(n);
// if 'n' is a perfect square
// it has odd number of factors
if
((root_n*root_n) == n)
return
false
;
// else 'n' has even
// number of factors
return
true
;
}
// Function to find and print
// status of each door
void
printStatusOfDoors(
int
n)
{
for
(
int
i=1; i<=n; i++)
{
// If even number of factors
// final status is closed
if
(hasEvenNumberOfFactors(i))
cout <<
"closed"
<<
" "
;
// else odd number of factors
// final status is open
else
cout <<
"open"
<<
" "
;
}
}