Dado n puertas y n personas. Las puertas están numeradas del 1 al n y las personas reciben identificaciones numeradas del 1 al n. Cada puerta puede tener solo 2 estados abierta y cerrada. Inicialmente todas las puertas tienen estado cerrado. Encuentra el estado final de todas las puertas si una persona cambia el estado actual de todas las puertas, es decir si de estado abierto cambia a estado cerrado y viceversa, para lo cual está autorizado. Una persona con id ‘i’ está autorizada a cambiar el estado de la puerta numerada ‘j’ si ‘j’ es un múltiplo de ‘i’.
Nota:
– Una persona tiene que cambiar el estado actual de todas las puertas para las que está autorizado exactamente una vez.
– Puede darse la situación de que antes de que una persona cambie el estado de la puerta, otra persona que también esté autorizada para la misma puerta cambie el estado de la puerta.
Ejemplo :
Input : 3 Output : open closed closed
Explicación: como n = 3, por lo tanto, hay
3 puertas {1, 2, 3} y
3 personas con id {1, 2, 3}
persona con id = 1 puede cambiar el estado de la puerta 1, 2, 3
persona con id = 2 puede cambiar el estado de la puerta 2
persona con id = 3 puede cambiar el estado de la puerta 3
Estado actual de todas las puertas: cerrado cerrado cerrado
Considere una secuencia de eventos,
- Persona con id = 1 cambia el estado de la puerta 2
Estado actual de todas las puertas: cerrado abierto cerrado - Persona con id = 3 cambia el estado de la puerta 3
Estado actual de todas las puertas: cerrado abierto abierto - Persona con id = 1 cambia el estado de la puerta 1, 3
Estado actual de todas las puertas: abierto abierto cerrado - Persona con id = 2 cambia el estado de la puerta 2
Estado actual de todas las puertas: abierto cerrado cerrado
Otro ejemplo :
Input : 5 Output : open closed closed open closed Note: Sequence of open/closed is displayed in increasing door number
Enfoque: Es un enfoque matemático y lógico. Si lo observamos correctamente, encontramos que el estado final de una puerta numerada i está abierta si ‘i’ tiene un número impar de factores y el estado está cerrado si ‘i’ tiene un número par de factores. No depende en qué secuencia se cambia el estado de las puertas. Para averiguar si el recuento de divisores de un número es par o impar, podemos ver Comprobar si el recuento de divisores es par o impar .
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>
Producción :
open closed closed open closed
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(1)
Referencias: Preguntado en una entrevista de TCS
Este artículo es una contribución de Aarti_Rathi y Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA