Número de puertas abiertas | Pregunta de codificación TCS

Considere un callejón largo con N puertas en un lado. Todas las puertas están cerradas inicialmente. Te mueves de un lado a otro en el callejón cambiando los estados de las puertas de la siguiente manera:

• Abres una puerta que ya está cerrada y cierras una puerta que ya está abierta.
• Empiezas en un extremo y sigues alterando el estado de las puertas hasta que llegas al otro extremo, y luego regresas y comienzas a alterar los estados de las puertas nuevamente.
• En el primer intento, modifica los estados de las puertas numeradas 1, 2, 3, … , N.
• En el segundo intento, modifica los estados de las puertas numeradas 2, 4, 6, … .
• En el tercer intento, alteras los estados de las puertas numeradas 3, 6, 9… .
• y así…

El procedimiento anterior continuará hasta el N ^-ésimo turno en el que altere el estado de la puerta numerada N. La tarea es encontrar el número de puertas abiertas al final del procedimiento.

Ejemplos:

Entrada: N = 3
Salida: 1

Entrada: N = 100
Salida: 10

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Una puerta solo puede estar abierta al final si y solo si tiene un número impar de factores porque cada puerta es visitada una vez por cada uno de sus factores .
• Inicialmente, todas las puertas están cerradas, por lo que permanecerá cerrada si tiene un número par de factores y permanecerá abierta si tiene un número impar de factores.
• Por lo tanto, el número total de puertas que quedan abiertas de 1 a N será el número de puertas que tienen un número impar de factores.

De las observaciones anteriores, solo el número que es cuadrado perfecto que tiene un número impar de factores. Por lo tanto, el número total de puertas que quedan abiertas de 1 a N será el número de cuadrados perfectos entre 1 y N , y el número de cuadrados perfectos entre 1 y N es sqrt(N) .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that counts the number of
// doors opens after the Nth turn
int countOpenDoors(int N)
{
 
    // Find the number of open doors
    int doorsOpen = sqrt(N);
 
    // Return the resultant count of
    // open doors
    return doorsOpen;
}
 
// Driver Code
int main()
{
 
    int N = 100;
    cout << countOpenDoors(N);
 
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
   
  // Function that counts the number of
// doors opens after the Nth turn
static int countOpenDoors(int N)
{
 
    // Find the number of open doors
    int doorsOpen = (int) Math.sqrt(N);
 
    // Return the resultant count of
    // open doors
    return doorsOpen;
}
 
// Driver Code
    public static void main (String[] args) {
        int N = 100;
        System.out.println(countOpenDoors(N));
 
    }
}
 
 // This code is contributed by Potta Lokesh

# Python3 code for the above approach
import math
 
# Function that counts the number of
# doors opens after the Nth turn
def countOpenDoors(N):
   
    # Find the number of open doors
    doorsOpen = int(math.sqrt(N))
     
    # Return the resultant count of
    # open doors
    return doorsOpen
 
# Driver Code
if __name__ == '__main__':
    N = 100
    print(countOpenDoors(N))
     
# This code is contributed by MuskanKalra1

using System;
 
class GFG {
 
    // Function that counts the number of
    // doors opens after the Nth turn
    static int countOpenDoors(int N)
    {
 
        // Find the number of open doors
        int doorsOpen = (int)Math.Sqrt(N);
 
        // Return the resultant count of
        // open doors
        return doorsOpen;
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 100;
        Console.Write(countOpenDoors(N));
    }
}
 
// This code is contributed by subhammahato348.

<script>
        // JavaScript program for the above approach
 
        // Function that counts the number of
        // doors opens after the Nth turn
        function countOpenDoors(N) {
 
            // Find the number of open doors
            let doorsOpen = parseInt(Math.sqrt(N));
 
            // Return the resultant count of
            // open doors
            return doorsOpen;
        }
 
        // Driver Code
 
        let N = 100;
        document.write(countOpenDoors(N));
 
    // This code is contributed by Potta Lokesh
 
    </script>

10

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)