The Hexed Stair of Vantressa's Tower
The sorceress Vantressa left her tower to the ravens and a stair of countless steps. Some of those steps are hexed, and a boot set on one of them wakes the wards. The Tower-Breakers' Lodge pays well for any climber who can pick a safe stride before the first step.
The steps are numbered 1, 2, 3, ... from the bottom. A climber with a stride of p sets foot on steps p, 2p, 3p, and so on, forever upward, and touches no other step. A stride is safe if none of the steps it touches is hexed.
Write safeStride(cursed, most):
cursedis a list of positive integers, the numbers of the hexed steps. It may be empty, unordered, and may contain duplicates.mostis a positive integer, the longest stride the climber can manage.
Return the smallest integer p with 1 <= p <= most such that the stride p is safe. That means no number in cursed is a multiple of p. If no stride in that range is safe, return -1.
examples
- case 1
cursed steps [4, 6, 9], longest stride 105. Stride 2 lands on 4, stride 3 lands on 6 and 9, and stride 4 lands on 4. Stride 5 misses all three. - case 2
cursed steps [2, 3, 4, 5, 6], longest stride 6-1. Every stride from 1 to 6 lands on at least one hexed step. - case 3
no cursed steps at all, longest stride 31. With nothing hexed, even a stride of 1 is safe.
- reward
- 220 XP
- signature
safeStride
TypeScript, run as ES2022 — types are stripped, not checked. If a JS engine would run it, so will we.
- first safe stride is five
- no cursed steps means stride one
- every stride blocked
- limit too short
- safe stride past many divisors
- single step with limit one
- single prime step
- step one cursed
- unordered with mixed factors
- answer equals the limit
- limit inclusive but blocked