> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/lcci/mian-shi-ti-16.11.md).

# 面试题 16.11

You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.

return all lengths in non-decreasing order.

Example:

Input: shorter = 1 longer = 2 k = 3 Output: {3,4,5,6} Note:

0 < shorter <= longer 0 <= k <= 100000

## Solutions

1. **hashset O(k)**

```cpp
class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k <= 0) return {};
        unordered_set<int> seen;
        for (int i = 0; i <= k; i++) {
            seen.insert(shorter * i + longer * (k - i));
        }
        vector<int> lens(seen.begin(), seen.end());
        sort(lens.begin(), lens.end());

        return lens;
    }
};
```

1. **math O(k)**
2. reference: <https://leetcode-cn.com/problems/diving-board-lcci/solution/qing-xi-yi-dong-de-shu-xue-tui-dao-che-di-nong-don/>
3. The key point is: length of all possible combinations of `(shorter * i + longer * (k - i))` are different than each other. Thus the hashset can be omitted.
   * This is true only when `shorter != longer`, otherwise their is only one answer.&#x20;
   * Proof:

```
len = f(i) = shorter * i + longer * (k - i)
           = shorter * i - longer * i + longer * k
           = (shorter - longer) * i + longer * k

As this is a monotonically decreasing function, `f(i)` is unique for each different i.
```

```cpp
class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k <= 0) return {};
        if (shorter == longer)
            return {shorter * k};

        vector<int> lens;
        for (int i = 0; i <= k; i++)
            lens.push_back(longer * i + shorter * (k - i));

        return lens;
    }
};
```