100 Doors
Updated
Problem statement
There are n doors in a row, numbered 1 to n, and all of them start closed. You make n passes along the row. On pass p (for p = 1, 2, ..., n) you toggle every door whose number is a multiple of p: a closed door opens and an open door closes.
Return the numbers of the doors that are open after all n passes, in increasing order.
Function
openDoors(n: int) → int[]Examples
Example 1
n = 10return = [1,4,9]Door 1 is toggled only on pass 1, so it ends open. Door 4 is toggled on passes 1, 2 and 4 (three times), so it ends open. Door 6 is toggled on passes 1, 2, 3 and 6 (four times), so it ends closed. Going through all ten doors this way leaves doors 1, 4 and 9 open.
Example 2
n = 1return = [1]There is one door and one pass, which opens it.
Example 3
n = 3return = [1]Pass 1 opens doors 1, 2 and 3. Pass 2 closes door 2. Pass 3 closes door 3. Only door 1 is open.
Constraints
1 <= n <= 10^5
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Generate an Unbiased Bit from a Biased CoinGoogle · ONSITE INTERVIEWGoogle interview questions
- Moving Cost by Volume and CategoryWayfair · ONSITE INTERVIEWWayfair interview questions
- Clock Hand Angle with Subsecond PrecisionScale AI · ONSITE INTERVIEWScale AI interview questions
- Recover the Initial Mango PileLSEG · ONSITE INTERVIEWLSEG interview questions
- Estimate Pi from Sampled PointsJP Morgan Chase · ONSITE INTERVIEWJP Morgan Chase interview questions
- Add Two Numeric Strings with CarryZipRecruiter · ONSITE INTERVIEWZipRecruiter interview questions
- Three- and Five-liter Jug PlanXilinx · ONSITE INTERVIEWXilinx interview questions
- Add Two Numbers Given as Digit ArraysCapital One · ONSITE INTERVIEWCapital One interview questions
- Babysitter Quote with Hourly RatesUpstart · ONSITE INTERVIEWUpstart interview questions
- Expected Value of Modified DiceJane Street · ONSITE INTERVIEWJane Street interview questions