You are given a strictly increasing integer array rungs
that represents the height of rungs on a ladder. You are currently on the floor at height 0
, and you want to reach the last rung.
You are also given an integer dist
. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is at most dist
. You are able to insert rungs at any positive integer height if a rung is not already there.
Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.
Example 1:
Input: rungs = [1,3,5,10], dist = 2 Output: 2 Explanation: You currently cannot reach the last rung. Add rungs at heights 7 and 8 to climb this ladder. The ladder will now have rungs at [1,3,5,7,8,10].
Example 2:
Input: rungs = [3,6,8,10], dist = 3 Output: 0 Explanation: This ladder can be climbed without adding additional rungs.
Example 3:
Input: rungs = [3,4,6,7], dist = 2 Output: 1 Explanation: You currently cannot reach the first rung from the ground. Add a rung at height 1 to climb this ladder. The ladder will now have rungs at [1,3,4,6,7].
Constraints:
1 <= rungs.length <= 105
1 <= rungs[i] <= 109
1 <= dist <= 109
rungs
is strictly increasing.
Solution: Math
Check two consecutive rungs, if their diff is > dist, we need insert (diff – 1) / dist rungs in between.
ex1 5 -> 11, diff = 6, dist = 2, (diff – 1) / dist = (6 – 1) / 2 = 2. => 5, 7, 9, 11.
ex2 0 -> 3, diff = 3, dist = 1, (diff – 1) / dist = (3 – 1) / 1 = 2 => 0, 1, 2, 3
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: int addRungs(vector<int>& rungs, int dist) { int ans = 0; for (size_t i = 0; i < rungs.size(); ++i) ans += (rungs[i] - (i ? rungs[i - 1] : 0) - 1) / dist; return ans; } }; |
Python3
1 2 3 4 |
# Author: Huahua class Solution: def addRungs(self, rungs: List[int], dist: int) -> int: return sum((r - 1 - (rungs[i - 1] if i else 0)) // dist for i, r in enumerate(rungs)) |