Gather k Tokens

Hard

You are given a strip of cells cells: cells[i] = 1 if cell i holds a token and 0 if it is empty. You need to collect exactly k tokens. At the start you pick one cell to stand on, once, and you never leave it. If that cell holds a token, you take it right away for free (the cell becomes empty). After that, each move is one of the following: - create a token in any empty cell other than yours; this can be done at most max_spawns times in total; - slide a token into an adjacent empty cell; if it lands on your cell, you take it immediately. Return the fewest moves needed to collect k tokens.

Example 1

cells=[1, 1, 0, 0, 1, 0, 1], k=3, max_spawns=0 → 4

Stand on cell 1: its token is free, the token from cell 0 takes 1 move, and the token from cell 4 takes three moves (4 → 3 → 2 → 1). That is 4 moves.

Example 2

cells=[0, 0, 0, 0], k=2, max_spawns=3 → 4

There are no real tokens: twice we spawn a token next to us and slide it in, 2 × 2 = 4 moves.

Example 3

cells=[1, 0, 0, 0, 0, 0, 1], k=2, max_spawns=1 → 2

Constraints

2 ≤ len(cells) ≤ 10⁵
cells[i] is 0 or 1
1 ≤ k ≤ 10⁵
0 ≤ max_spawns ≤ 10⁵
sum(cells) + max_spawns ≥ k

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Prefix Sum Sliding Window

Similar problems

Friends in One Row Hard Signal in the Remotest Village Hard Even Out With Increments Medium Rug Over Painted Stretches Medium Richest Row of Houses Medium

Input

cells=[1, 1, 0, 0, 1, 0, 1], k=3, max_spawns=0

Expected

Run checks the first 3 tests in your browser. Submit checks all 98 tests on the server, hidden ones included.