1063. Switches After n Rounds
A long hallway has n wall switches numbered 1 to n, all OFF to begin with. A caretaker then walks the hallway n times. On walk k they press every k-th switch (switch k, switch 2k, switch 3k, and so on), and each press flips that switch between OFF and ON. So walk 1 presses every switch, walk 2 presses every second one, and so forth until walk n presses only the last switch.
Return how many switches are ON once all n walks are finished. Because n can be around two billion, replaying the walks is far too slow; you should be able to answer in O(1) time and O(1) space.
Example 1
- Input:
- n = 16
- Output:
- 4
- Explanation:
The switches that stay ON are numbers 1, 4, 9 and 16, which are the perfect squares up to 16.
Example 2
- Input:
- n = 50
- Output:
- 7
- Explanation:
The perfect squares up to 50 are 1, 4, 9, 16, 25, 36 and 49, giving seven switches left on.
Constraints
0 ≤ n ≤ 2 * 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(1)
- Space
- O(1)