Tree Toggles with Periodic Permanent Locks
IMC Trading● MediumNEW GRADOAProblem statement
There are n trees numbered from 1 through n. Every tree starts dormant and unlocked.
Process nights 1 through nights in increasing order. On night d, toggle every unlocked tree whose number is a multiple of d: dormant becomes active, and active becomes dormant.
On every night divisible by lockPeriod, permanently lock each currently active tree. A locked tree remains active and cannot be toggled on any later night. Dormant trees are not locked.
For this exercise, assume that a night's toggles happen before its locking event. For this exercise, assume the tree count, night count and lock period generalize the reported values 225, 225 and 30.
Return the total number of active trees after the final night, including locked active trees. Zero trees or zero nights gives zero.
Complete countActiveTrees(n, nights, lockPeriod).
Function
countActiveTrees(n: int, nights: int, lockPeriod: int) → intExamples
Example 1
n = 225nights = 225lockPeriod = 30return = 200Apply the nightly toggles and lock active trees after nights 30,60,90,120,150,180,210. Counting the final states gives 200 active trees. Without locking, only the fifteen perfect-square-numbered trees would remain active; that is a different process.
Example 2
n = 2nights = 2lockPeriod = 2return = 1Night 1 activates both trees. Night 2 toggles tree 2 back to dormant, then locks active tree 1. Exactly one tree is active.
Example 3
n = 5nights = 3lockPeriod = 1return = 5Night 1 activates and then permanently locks every tree. Later nights cannot change them.
Example 4
n = 4nights = 0lockPeriod = 2return = 0No night occurs, so every tree remains dormant.
Constraints
- For this exercise, assume
0 <= n <= 2000,0 <= nights <= 2000and1 <= lockPeriod <= 2000. - Tree numbers and night numbers are one-based.
- A lock is permanent and applies only to a tree active immediately after that night's toggles.