Количество открытых дверей | Вопрос по кодированию TCS

Рассмотрим длинный переулок с N дверями с одной стороны. Изначально все двери закрыты. Вы двигаетесь туда-сюда по переулку, меняя состояние дверей следующим образом:

• Вы открываете дверь, которая уже закрыта, и закрываете дверь, которая уже открыта.
• Вы начинаете с одного конца и продолжаете изменять состояние дверей, пока не дойдете до другого конца, а затем возвращаетесь и снова начинаете изменять состояние дверей.
• В первый раз вы меняете состояние дверей с номерами 1, 2, 3, …, N .
• На втором этапе вы меняете состояние дверей с номерами 2, 4, 6, … .
• На третьем этапе вы меняете состояние дверей с номерами 3, 6, 9… .
• и так далее…

Описанная выше процедура будет продолжаться до N ^-го хода , в котором вы измените состояние двери с номером N. Задача состоит в том, чтобы найти количество открытых дверей в конце процедуры.

Примеры:

Input: N = 3
Output: 1

Input: N = 100
Output: 10

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Дверь может быть открыта в конце только тогда и только тогда, когда она имеет нечетное число факторов, потому что каждая дверь посещается один раз каждым из ее факторов.
• Изначально все двери закрыты, поэтому она останется закрытой, если у нее четное количество факторов, и останется открытой, если у нее нечетное количество факторов.
• Следовательно, общее количество дверей, которые остаются открытыми от 1 до N , будет количеством дверей, имеющих нечетное количество множителей.

Из приведенных выше наблюдений видно, что только числа, являющиеся совершенными квадратами, имеют нечетное число множителей. Следовательно, общее количество дверей, которые остаются открытыми от 1 до N , будет равно количеству полных квадратов от 1 до N, а количество полных квадратов от 1 до N равно sqrt(N) .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log N)
Вспомогательное пространство: O(1)