检查门是开着还是关着-yiteyi-C++库

给定n个门和n个人。门的编号为1至n，人员的id编号为1至n。每个门只能有2个打开和关闭状态。最初，所有的门都处于关闭状态。如果一个人更改了所有门的当前状态，即如果状态为打开，则更改为关闭状态，反之亦然，则查找所有门的最终状态，并获得授权。如果“j”是“i”的倍数，则id为“i”的人员有权更改编号为“j”的门的状态。注： –一个人必须更改其授权的所有车门的当前状态一次。 –可能存在这样一种情况：在一个人更改门的状态之前，另一个同样被授权使用同一扇门的人会更改门的状态。 例子：

null

Input : 3Output : open closed closed

说明： 因为n=3，所以有三扇门{1,2,3}和 3名身份证为{1,2,3}的人 id=1的人可以更改门1、2、3的状态 id=2的人可以更改门2的状态 id=3的人可以更改门3的状态所有门的当前状态：关闭考虑一系列事件，

id=1的人员更改门2的状态所有门的当前状态：关闭打开关闭
id=3的人员更改门3的状态所有门的当前状态：关闭-打开-打开
id=1的人员更改门1、3的状态所有门的当前状态：打开-关闭
id=2的人员更改门2的状态所有门的当前状态：打开关闭关闭

另一个例子：

Input : 5Output : open closed closed open closedNote: Sequence of open/closed is displayed inincreasing door number

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 这是一种数学和逻辑的方法。如果我们仔细观察，就会发现门的最终状态我如果“i”有奇数个因素，则状态为打开；如果“i”有偶数个因素，则状态为关闭。它不取决于车门状态的更改顺序。为了找出数的除数是偶数还是奇数，我们可以看到检查除数的计数是偶数还是奇数邮递

C++

                         // C++ implementation of                       
                         // doors open or closed                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // 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"                                     <<                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5;                       
                                                 printStatusOfDoors(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // java implementation of                       
                         // doors open or closed                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Function to check whether 'n'                       
                                                 // has even number of factors or not                       
                                                 static                                     boolean                                     hasEvenNumberOfFactors(                                     int                                     n)                       
                                                 {                       
                                                 double                                     root_n = Math.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                       
                                                 static                                     void                                     printStatusOfDoors(                                     int                                     n)                       
                                                 {                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 // If even number of factors                       
                                                 // final status is closed                       
                                                 if                                     (hasEvenNumberOfFactors(i))                       
                                                 System .out.print(                                     "closed"                                     +                                     " "                                     );                       
                                   
                                                 // else odd number of factors                       
                                                 // final status is open                       
                                                 else                       
                                                 System.out.print(                                     "open"                                     +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                                                 // Driver program                       
                                                 public                                     static                                     void                                     main (String[] args) {                       
                                                 int                                     n =                                     5                                     ;                       
                                                 printStatusOfDoors(n);                       
                                   
                                                 }                       
                         }                       
           
                         // This article is contributed by vt_m                       

Python3

                         # Python 3 implementation of                       
                         # doors open or closed                       
                         import                                     math                       
           
                         # Function to check whether                       
                         # 'n' has even number of                       
                         # factors or not                       
                         def                                     hasEvenNumberOfFactors(n):                       
           
                                                 root_n                                     =                                     math.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                       
                         def                                     printStatusOfDoors(n):                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                   
                                                 # If even number of factors                       
                                                 # final status is closed                       
                                                 if                                     (hasEvenNumberOfFactors(i)                                     =                                     =                                     True                                     ):                       
                                                 print                                     (                                     "closed"                                     , end                                     =                                     " "                                     )                       
           
                                                 # else odd number of factors                       
                                                 # final status is open                       
                                                 else                                     :                       
                                                 print                                     (                                     "open"                                     , end                                     =                                     " "                                     )                       
                                   
                         # Driver program                       
                         n                                     =                                     5                       
           
                         printStatusOfDoors(n)                       
           
                         # This code is contributed by Smitha Dinesh Semwal                       

C#

                         // C# implementation of                       
                         // doors open or closed                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                         // Function to check whether                       
                         // 'n' has even number of                       
                         // factors or not                       
                         static                                     bool                                     hasEvenNumberOfFactors(                                     int                                     n)                       
                         {                       
                                                 double                                     root_n = Math.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                       
                         static                                     void                                     printStatusOfDoors(                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 1 ; i <= n; i++)                       
                                                 {                       
                                                 // If even number of factors                       
                                                 // final status is closed                       
                                                 if                                     (hasEvenNumberOfFactors(i))                       
                                                 Console.Write(                                     "closed"                                     +                                     " "                                     );                       
           
                                                 // else odd number of factors                       
                                                 // final status is open                       
                                                 else                       
                                                 Console.Write(                                     "open"                                     +                                     " "                                     );                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     n = 5;                       
                                                 printStatusOfDoors(n);                       
                         }                       
                         }                       
           
                         // This Code is contributed by ajit                       

PHP

                         <?php                       
                         // PHP implementation of                       
                         // doors open or closed                       
           
                         // Function to check whether                       
                         // 'n' has even number of                       
                         // factors or not                       
           
                         function                                     hasEvenNumberOfFactors(                                     $n                                     )                       
                         {                       
                                                 $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                       
                         function                                     printStatusOfDoors(                                     $n                                     )                       
                         {                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // If even number of factors                       
                                                 // final status is closed                       
                                                 if                                     (hasEvenNumberOfFactors(                                     $i                                     ))                       
                                                 echo                                     "closed"                                     ,                                     " "                                     ;                       
           
                                                 // else odd number of factors                       
                                                 // final status is open                       
                                                 else                       
                                                 echo                                     "open"                                     ,                                     " "                                     ;                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 5;                       
                         printStatusOfDoors(                                     $n                                     );                       
           
                         // This code is contributed by ajit@                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program for the above approach                       
           
                                                 // Function to check whether 'n'                       
                                                 // has even number of factors or not                       
                                                 function                                     hasEvenNumberOfFactors(n)                       
                                                 {                       
                                                 let root_n = Math.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                       
                                                 function                                     printStatusOfDoors(n)                       
                                                 {                       
                                                 for                                     (let i = 1 ; i <= n; i++)                       
                                                 {                       
                                                 // If even number of factors                       
                                                 // final status is closed                       
                                                 if                                     (hasEvenNumberOfFactors(i))                       
                                                 document.write(                                     "closed"                                     +                                     " "                                     );                       
                                   
                                                 // else odd number of factors                       
                                                 // final status is open                       
                                                 else                       
                                                 document.write(                                     "open"                                     +                                     " "                                     );                       
                                                 }                       
                                                 }                       
                                   
                         // Driver Code                       
                                   
                                                 let n = 5;                       
                                                 printStatusOfDoors(n);                       
           
                         // This code is contributed by susmitakundugoaldanga.                       
                         </script>                       

输出：

open closed closed open closed

时间复杂性： O（n）参考资料：在接受TCS采访时问道本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章