Skip to content

16.11. Diving Board

Description

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

Solution 1: Case Analysis

Thinking

\(k\) planks, each short or long. Recursing over \(2^k\) assignments overcounts; there are at most \(k+1\) distinct sums.

\(i\) long planks give \(i\cdot longer+(k-i)\cdot shorter\). \(k=0\) is empty; equal lengths collapse to one value.

When the lengths differ, \(i=0\ldots k\) is strictly increasing, so the loop needs no deduplication.

If \(k=0\), there is no solution, and we can directly return an empty list.

If \(shorter=longer\), we can only use a board with length \(longer \times k\), so we directly return a list with length \(longer \times k\).

Otherwise, we can use a board with length \(shorter \times (k-i) + longer \times i\), where \(0 \leq i \leq k\). We enumerate \(i\) in the range \([0, k]\), and calculate the corresponding length. For different values of \(i\), we will not get the same length, because if \(0 \leq i \lt j \leq k\), then the difference in length is \((i - j) \times (longer - shorter) \lt 0\). Therefore, for different values of \(i\), we will get different lengths.

The time complexity is \(O(k)\), where \(k\) is the number of boards. Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        if k == 0:
            return []
        if longer == shorter:
            return [longer * k]
        ans = []
        for i in range(k + 1):
            ans.append(longer * i + shorter * (k - i))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) {
            return new int[0];
        }
        if (longer == shorter) {
            return new int[] {longer * k};
        }
        int[] ans = new int[k + 1];
        for (int i = 0; i < k + 1; ++i) {
            ans[i] = longer * i + shorter * (k - i);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k == 0) return {};
        if (longer == shorter) return {longer * k};
        vector<int> ans;
        for (int i = 0; i < k + 1; ++i)
            ans.push_back(longer * i + shorter * (k - i));
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func divingBoard(shorter int, longer int, k int) []int {
    if k == 0 {
        return []int{}
    }
    if longer == shorter {
        return []int{longer * k}
    }
    var ans []int
    for i := 0; i < k+1; i++ {
        ans = append(ans, longer*i+shorter*(k-i))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function divingBoard(shorter: number, longer: number, k: number): number[] {
    if (k === 0) {
        return [];
    }
    if (longer === shorter) {
        return [longer * k];
    }
    const ans: number[] = [k + 1];
    for (let i = 0; i <= k; ++i) {
        ans[i] = longer * i + shorter * (k - i);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    func divingBoard(_ shorter: Int, _ longer: Int, _ k: Int) -> [Int] {
        if k == 0 {
            return []
        }
        if shorter == longer {
            return [shorter * k]
        }

        var ans = [Int](repeating: 0, count: k + 1)
        for i in 0...k {
            ans[i] = longer * i + shorter * (k - i)
        }
        return ans
    }
}

Comments