There are n doors numbered 1 to n and n people numbered 1 to n. Every door is…
2026
There are n doors numbered 1 to n and n people numbered 1 to n. Every door is closed to begin with. The people act one after another, from person 1 up to person n. Person i toggles the status of every ith door, that is, every door whose number is a multiple of i: a closed door becomes open and an open door becomes closed. After all n people have acted exactly once, print the final status of all n doors, where 1 means open and 0 means closed.
Input format: The only token on standard input is the integer n.
Output format: Print n values separated by single spaces, the final status of door 1, door 2, ..., door n in that order, where 1 means open and 0 means closed, followed by a newline.
Examples:
Input: 3
Output: 1 0 0
Explanation: Every door starts closed, so the status is (0 0 0). Person 1 toggles doors 1, 2 and 3, giving (1 1 1). Person 2 toggles door 2, giving (1 0 1). Person 3 toggles door 3, giving (1 0 0).
Input: 2
Output: 1 0
Explanation: Every door starts closed, so the status is (0 0). Person 1 toggles doors 1 and 2, giving (1 1). Person 2 toggles door 2, giving (1 0).
Constraints:
1 ≤ n ≤ 104
Attempted by 9 students.
Show answer & explanation
Concept — the final state of a door is decided by nothing except the parity of the number of times it is toggled. Person i touches door d exactly when i divides d, so door d is toggled once for every divisor of d, and the total number of toggles it receives is the divisor count of d. Every divisor of d is at most d, and d is at most n, so every divisor of d belongs to a person who actually acts and no toggle is lost. Each toggle flips the state and every door starts closed, so a door finishes open exactly when its divisor count is odd. Divisors come in pairs (i, d / i), and the two members of a pair are different numbers unless i = d / i, that is unless d = i × i. A pairing therefore leaves an unmatched divisor only for a perfect square, so the divisor count of d is odd exactly when d is a perfect square. Door d finishes open if and only if d is a perfect square.
Applying this to the problem:
Read the single integer n.
Create a status array of n values and set every entry to 0, meaning closed.
Walk i = 1, 2, 3, ... while i × i ≤ n, and set the entry for door i × i to 1. These are exactly the perfect squares 1, 4, 9, 16, ... that do not exceed n, so the loop runs ⌊√n⌋ times and touches each open door once.
Print the n entries in order, separated by single spaces.
Cost: the marking loop performs about √n steps and the printing performs n steps, so the running time is O(n), dominated by producing the output, with O(n) memory for the status array. The direct simulation of every person toggling every multiple is also fast enough at n ≤ 104, because its work is n / 1 + n / 2 + ... + n / n, which is about n × ln n, but the perfect-square rule is the insight the problem is testing.
Cross-check against the samples and one larger case:
n = 3: the only perfect square not exceeding 3 is 1, so the output is 1 0 0. The step-by-step simulation agrees, (0 0 0) → (1 1 1) → (1 0 1) → (1 0 0).
n = 2: the only perfect square not exceeding 2 is 1, so the output is 1 0, which is the second sample.
n = 10: the perfect squares are 1, 4 and 9, so the output is 1 0 0 1 0 0 0 0 1 0. The divisor counts confirm it, because door 4 has the three divisors 1, 2, 4, an odd count, while door 6 has the four divisors 1, 2, 3, 6, an even count.
Pitfall — print every one of the n values, including the trailing zeros, because an output that stops early is wrong even when the marked doors are right. Prefer the integer test i × i ≤ n over a floating-point square root when deciding which doors are perfect squares: the integer form is exact by construction, while a rounded square root has to be corrected by hand at boundary values once the bound on n grows.