A traveler needs to stay for n days in a hotel outside town. He is out of cash and his credit card is expired. But he has a gold chain with n links.
The rule in this hotel is that residents should pay their rent every morning. The traveler comes to an agreement with the manager to pay one link of the golden chain for each day. But the manager also demands that the traveler should make the least possible damage to the chain while paying every day. In other words, he has to come up with a solution to cut as few links as possible.
Cutting a link creates three subchains: one containing only the cut link, and one on each side. For example, cutting the third link of a chain of length 8 creates subchains of length [2, 1, 5]. The manager is happy to make change, so the traveller can pay the first day with the chain of length 1, then the second day with the chain of length 2, getting the first chain back.
Your code should input the length n, and output a list of links to cut of minimum length.
Rules:
- n is an integer > 0.
- You can use either 0-based or 1-based indexing for the links.
- For some numbers, the solution is not unique. For example, if
n = 15
both[3, 8]
and[4, 8]
are valid outputs. - You can either return the list, or print it with any reasonable separator.
- This is code-golf, so the shortest code in bytes wins.
Test cases:
Input Output (1-indexed)
1 []
3 [1]
7 [3]
15 [3, 8]
149 [6, 17, 38, 79]
Detailed example
For n = 15, cutting the links 3 and 8 results in subchains of length [2, 1, 4, 1, 7]
. This is a valid solution because:
1 = 1
2 = 2
3 = 1+2
4 = 4
5 = 1+4
6 = 2+4
7 = 7
8 = 1+7
9 = 2+7
10 = 1+2+7
11 = 4+7
12 = 1+4+7
13 = 2+4+7
14 = 1+2+4+7
15 = 1+1+2+4+7
No solution with only one cut exists, so this is an optimal solution.
Addendum
Note that this problem is related to integer partitioning. We're looking for a partition P of n such that all integers from 1 to n have at least one patition that is a subset of P.
Here's a YouTube video about one possible algorithm for this problem.
1+2
. Where did the second 2-link-chain come from? \$\endgroup\$