values and an integer cap. In one operation you may pick two adjacent elements a and b with a · b ≤ cap and replace them with a single element equal to a · b. You may perform any number of operations, including none.
For example, with cap = 6 the array [1, 3, 2, 4] can become [3, 2, 4] or [1, 6, 4], but not [1, 3, 8].
Return the smallest length the array can be reduced to.values=[2, 5, 1, 3, 4], cap=12 → 2
[2, 5, 1, 3, 4] → [10, 1, 3, 4] → [10, 3, 4] → [10, 12]. 10 and 12 cannot merge: 120 > 12.
values=[4, 0, 9, 9], cap=1 → 1
A zero merges with any neighbour into another zero, so the whole array collapses into one number.
values=[5, 7], cap=30 → 2
5 · 7 = 35 > 30, so nothing can be merged.
values=[2, 5, 1, 3, 4], cap=12
2
Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.