# 1936. Add Minimum Number of Rungs

## Description

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.
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:


Example 3:

Input: rungs = [3,4,6,7], dist = 2
Output: 1
Explanation:
You currently cannot reach the first rung from the ground.
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.

## Solutions

Solution 1: Greedy + Simulation

According to the problem description, we know that every time we plan to climb a new rung, we need to ensure that the height difference between the new rung and the current position does not exceed dist. Otherwise, we need to greedily insert a new rung at a distance of $dist$ from the current position, climb a new rung, and the total number of rungs to be inserted is $\lfloor \frac{b - a - 1}{dist} \rfloor$, where $a$ and $b$ are the current position and the height of the new rung, respectively. The answer is the sum of all inserted rungs.

The time complexity is $O(n)$, where $n$ is the length of rungs. The space complexity is $O(1)$.

• class Solution {
public int addRungs(int[] rungs, int dist) {
int ans = 0, prev = 0;
for (int x : rungs) {
ans += (x - prev - 1) / dist;
prev = x;
}
return ans;
}
}

• class Solution {
public:
int addRungs(vector<int>& rungs, int dist) {
int ans = 0, prev = 0;
for (int& x : rungs) {
ans += (x - prev - 1) / dist;
prev = x;
}
return ans;
}
};

• class Solution:
def addRungs(self, rungs: List[int], dist: int) -> int:
rungs = [0] + rungs
return sum((b - a - 1) // dist for a, b in pairwise(rungs))


• func addRungs(rungs []int, dist int) (ans int) {
prev := 0
for _, x := range rungs {
ans += (x - prev - 1) / dist
prev = x
}
return
}

• function addRungs(rungs: number[], dist: number): number {
let ans = 0;
let prev = 0;
for (const x of rungs) {
ans += ((x - prev - 1) / dist) | 0;
prev = x;
}
return ans;
}


• impl Solution {
pub fn add_rungs(rungs: Vec<i32>, dist: i32) -> i32 {
let mut ans = 0;
let mut prev = 0;

for &x in rungs.iter() {
ans += (x - prev - 1) / dist;
prev = x;
}

ans
}
}