Рубрики

Проверьте, открыта ли дверь или закрыта

Математика

Дано n дверей и n человек. Двери пронумерованы от 1 до n, и людям даны номера с номерами от 1 до n. Каждая дверь может иметь только 2 статуса открытых и закрытых. Изначально все двери имеют статус закрытых. Найти окончательный статус всех дверей, если человек изменяет текущий статус всех дверей, то есть, если статус открыт, то изменить на статус закрыт и наоборот, для которого он авторизован. Лицо с идентификатором «i» имеет право изменять статус двери с номером «j», если «j» кратно «i».

Замечания:
— Человек должен изменить текущее состояние всех дверей, на которые он авторизован, только один раз.
— Может возникнуть ситуация, когда до того, как человек меняет статус двери, другой человек, который также авторизован для той же двери, меняет статус двери.
Пример :

Input : 3
Output : open closed closed

Пояснение: Поскольку n = 3, следовательно, есть
3 двери {1, 2, 3} и
3 человека с идентификаторами {1, 2, 3}

человек с id = 1 может изменить статус двери 1, 2, 3
человек с id = 2 может изменить статус двери 2
человек с id = 3 может изменить статус двери 3

Текущее состояние всех дверей: закрыто закрыто закрыто
Рассмотрим последовательность событий,

  1. Человек с id = 1 меняет статус двери 2
    Текущее состояние всех дверей: закрыто открыто закрыто
  2. Человек с id = 3 меняет статус двери 3
    Текущее состояние всех дверей: закрыто открыто открыто
  3. Человек с id = 1 меняет статус двери 1, 3
    Текущее состояние всех дверей: открыто открыто закрыто
  4. Человек с id = 2 меняет статус двери 2
    Текущее состояние всех дверей: открыто закрыто закрыто

    5. В этой последовательности все лица изменили текущее состояние всех дверей ровно один раз, для которых они авторизованы.

Другой пример :

Input : 5
Output : open closed closed open closed

Note: Sequence of open/closed is displayed in
increasing door number

Подход: это математический и логический подход. Если мы наблюдаем это должным образом, то мы обнаруживаем, что окончательный статус двери с номером i открыт, если у «i» есть нечетное количество факторов, и статус закрыт, если у «i» есть четное количество факторов. Это не зависит от того, в какой последовательности изменяется статус дверей. Чтобы выяснить, является ли число делителей числа четным или нечетным, мы можем посмотреть Проверить, является ли число делителей четным или нечетным постом.

C ++

// C ++ реализация
// двери открыты или закрыты
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки, 'n'
// имеет четное количество факторов или нет

bool hasEvenNumberOfFactors(int n)

{

    int root_n = sqrt(n);

  

    // если 'n' - идеальный квадрат

    // имеет нечетное количество факторов

    if ((root_n*root_n) == n)

        return false;

  

    // иначе 'n' имеет даже

    // количество факторов

    return true;

}

  
// Функция поиска и печати
// статус каждой двери

void printStatusOfDoors(int n)

{

    for (int i=1; i<=n; i++)

    {

        // Если четное число факторов

        // окончательный статус закрыт

        if (hasEvenNumberOfFactors(i))

            cout << "closed" << " ";

  

        // еще нечетное количество факторов

        // окончательный статус открыт

        else

            cout << "open" << " ";

    }

}

  
// Драйвер программы

int main()

{

    int n = 5;

    printStatusOfDoors(n);

    return 0;

}

Джава

// Java-реализация
// двери открыты или закрыты

import java.io.*;

  

class GFG {

      

    // Функция для проверки, 'n'

    // имеет четное количество факторов или нет

    static boolean hasEvenNumberOfFactors(int n)

    {

        double root_n = Math.sqrt(n);

      

        // если 'n' - идеальный квадрат

        // имеет нечетное количество факторов

        if ((root_n*root_n) == n)

            return false;

      

        // иначе 'n' имеет даже

        // количество факторов

        return true;

    }

      

    // Функция поиска и печати

    // статус каждой двери

    static void printStatusOfDoors(int n)

    {

        for (int i = 1 ; i <= n; i++)

        {

            // Если четное число факторов

            // окончательный статус закрыт

            if (hasEvenNumberOfFactors(i))

                System .out.print( "closed" + " ");

      

            // еще нечетное количество факторов

            // окончательный статус открыт

            else

                System.out.print( "open" + " ");

        }

    }

      

    // Драйвер программы

    public static void main (String[] args) {

        int n = 5;

        printStatusOfDoors(n);

          

    }

}

  
// Эта статья предоставлена vt_m

python3

# Python 3 реализация
# двери открыты или закрыты

import math

  
# Функция для проверки
# 'n' имеет четное число
# факторов или нет

def hasEvenNumberOfFactors(n):

  

    root_n = math.sqrt(n) 

  

    # если 'n' - идеальный квадрат

    # имеет нечетное количество факторов

    if ((root_n * root_n) == n):

        return False

  

    # еще «н» имеет даже

    # количество факторов

    return True

  
# Функция поиска и печати
# статус каждой двери

def printStatusOfDoors(n):

  

    for i in range(1, n + 1):

      

        # Если чётное количество факторов

        # окончательный статус закрыт

        if (hasEvenNumberOfFactors(i) == True):

            print("closed", end =" ") 

  

        # еще нечетное количество факторов

        # окончательный статус открыт

        else:

            print("open", end =" ") 

      
# Драйверная программа

n = 5

  
printStatusOfDoors(n) 

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # реализация
// двери открыты или закрыты

using System;

  

class GFG

{

  
// Функция для проверки
// 'n' имеет четное число
// факторы или нет

static bool hasEvenNumberOfFactors(int n)

{

    double root_n = Math.Sqrt(n);

  

    // если 'n' - идеальный квадрат

    // имеет нечетное количество факторов

    if ((root_n * root_n) == n)

        return false;

  

    // иначе 'n' имеет даже

    // количество факторов

    return true;

}

  
// Функция поиска и печати
// статус каждой двери

static void printStatusOfDoors(int n)

{

    for (int i = 1 ; i <= n; i++)

    {

        // Если четное число факторов

        // окончательный статус закрыт

        if (hasEvenNumberOfFactors(i))

            Console.Write("closed" + " ");

  

        // еще нечетное количество факторов

        // окончательный статус открыт

        else

            Console.Write("open" + " ");

    }

}

  
// Код драйвера

static public void Main ()

{

    int n = 5;

    printStatusOfDoors(n);

}
}

  
// Этот код предоставлен ajit

PHP

<?php
// PHP реализация
// двери открыты или закрыты

  
// Функция для проверки
// 'n' имеет четное число
// факторы или нет

  

function hasEvenNumberOfFactors($n)

{

    $root_n = sqrt($n);

  

    // если 'n' - идеальный квадрат

    // имеет нечетное количество факторов

    if (($root_n * $root_n) == $n)

        return false;

  

    // иначе 'n' имеет даже

    // количество факторов

    return true;

}

  
// Функция поиска и печати
// статус каждой двери

function printStatusOfDoors($n)

{

    for ($i = 1; $i <= $n; $i++)

    {

        // Если четное число факторов

        // окончательный статус закрыт

        if (hasEvenNumberOfFactors($i))

            echo "closed" ," ";

  

        // еще нечетное количество факторов

        // окончательный статус открыт

        else

            echo "open" ," ";

    }

}

  
// Код драйвера

$n = 5;

printStatusOfDoors($n);

  
// Этот код предоставлен ajit @
?>


Выход :

open closed closed open closed

Временная сложность: O (n)

Рекомендации: Спрошено в интервью TCS
Эта статья предоставлена Аюшем Джаухари . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте, открыта ли дверь или закрыта

0.00 (0%) 0 votes