Valleys in the Folded Strip
Fold a long strip of paper in half folds times, always laying the right half over the left half. Open it again and read the creases from left to right: each one is a valley v or a peak p.
One fold leaves v. Every further fold keeps the old pattern, puts a new v after it, and then adds the old pattern once more, read backwards with every crease flipped. So two folds give vvp and three folds give vvpvvpp.
Return how many of the first k creases are valleys.
Example 1
folds 3
k 5
returns 4
The first five creases of vvpvvpp are vvpvv: four valleys.
Example 2
folds 2
k 3
returns 2
All of vvp: two valleys.
Example 3
folds 1
k 1
returns 1
The only crease is a valley.
Constraints
1 <= folds <= 501 <= k <= 2**folds - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Count the BoxesBeginner
- Digit TallyBeginner
- Equal NeighboursBeginner
- Halving TotalBeginner
- Largest DigitBeginner
- Multiply It OutBeginner
- Nested SumBeginner
- Rising DigitsBeginner