# Add Minimum Number of Rungs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/add-minimum-number-of-rungs)
Canonical: https://scaleengineer.com/dsa/problems/add-minimum-number-of-rungs
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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**.

# Approaches
## Brute Force Simulation
This approach simulates the process of climbing the ladder. We iterate through the rungs, and for each gap between the current position and the next rung, we check if it's climbable. If the gap is too large, we simulate adding rungs one by one, each time advancing our position by `dist`, until the next rung is reachable.
**Time:** O(S / dist), where S is the height of the last rung. The complexity is not dependent on N (the number of rungs) but on the magnitude of the values in `rungs`. In the worst case, `rungs = [10^9]` and `dist = 1`, the inner loop can run up to 10^9 times, which is too slow. · **Space:** O(1), as we only use a few variables to store the current state, regardless of the input size.
**Pros:** Simple to understand and implement as it directly mirrors the problem statement.
**Cons:** Extremely inefficient for large gaps between rungs or a small `dist` value.; Will likely result in a Time Limit Exceeded (TLE) error for many test cases due to its high time complexity.
### Explanation
This method directly models the physical process of climbing. We maintain a variable `currentHeight` representing our current position on the ladder (initially 0, the floor) and a counter `rungsAdded` for the number of rungs we add.

We iterate through the `rungs` array, considering each rung as our next target. For each `targetRung`, we check if the difference `targetRung - currentHeight` is greater than `dist`. If it is, we are unable to make the climb in one step. We then enter a loop where we repeatedly add a rung. In each iteration of this inner loop, we increment `rungsAdded` and advance our `currentHeight` by `dist`. This loop continues until the remaining distance to `targetRung` is less than or equal to `dist`.

Once the `targetRung` is reachable, we update `currentHeight` to the height of the `targetRung` and move to the next rung in the array. This process is repeated for all rungs, and the final value of `rungsAdded` is the result.

```java
class Solution {
    public int addRungs(int[] rungs, int dist) {
        int rungsAdded = 0;
        int currentHeight = 0;
        for (int rung : rungs) {
            // While the next rung is unreachable
            while (rung - currentHeight > dist) {
                // Add a rung at the maximum possible distance
                currentHeight += dist;
                rungsAdded++;
            }
            // Climb to the existing rung
            currentHeight = rung;
        }
        return rungsAdded;
    }
}
```
### Algorithm
- Initialize `rungsAdded = 0` and `currentHeight = 0`.
- For each `rung` in the `rungs` array:
  - While the gap `rung - currentHeight` is greater than `dist`:
    - Increment `rungsAdded` as we need to add a rung.
    - Advance our position by `dist`: `currentHeight += dist`.
  - Once the current `rung` is reachable, update `currentHeight = rung`.
- Return `rungsAdded`.

## Greedy Approach with Mathematical Calculation
This approach improves upon the simulation by calculating the number of rungs needed for a large gap in a single mathematical operation instead of simulating each step. It's a greedy approach because for each gap, we add the minimum number of rungs required to bridge it, and this local optimization leads to a global optimum since choices for one gap don't affect subsequent gaps.
**Time:** O(N), where N is the number of rungs in the input array. We iterate through the array once, and each step involves a constant number of arithmetic operations. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Highly efficient and optimal solution with linear time complexity.; Handles large values of rung heights and distances without performance degradation.
**Cons:** Requires a small mathematical insight to derive the formula, which might be slightly less intuitive than direct simulation.
### Explanation
This optimal solution avoids the slow simulation of the brute-force approach. We iterate through the rungs once, keeping track of our `currentHeight` (starting at 0).

For each `rung`, we calculate the `gap = rung - currentHeight`. If this `gap` is larger than `dist`, we must add rungs. To find the minimum number of rungs to add, we should place them as far apart as possible, i.e., at a distance of `dist` from each other. The number of rungs needed to cover a `gap` can be calculated efficiently with the formula `(gap - 1) / dist` using integer division. This formula correctly computes `ceil(gap / dist) - 1`.

For example, if the gap is 5 and dist is 2, `(5-1)/2 = 2` rungs are needed. We add this calculated number to our total count of `rungsAdded`.

After processing the gap (and adding rungs if necessary), we update our `currentHeight` to the height of the current `rung`. We continue this for all rungs and return the total count.

```java
class Solution {
    public int addRungs(int[] rungs, int dist) {
        int rungsAdded = 0;
        int currentHeight = 0;
        for (int rung : rungs) {
            int gap = rung - currentHeight;
            if (gap > dist) {
                // Calculate how many rungs are needed for this gap.
                // Each new rung can cover 'dist' height.
                // The number of rungs needed is ceil(gap / dist) - 1.
                // Using integer arithmetic, this is (gap - 1) / dist.
                rungsAdded += (gap - 1) / dist;
            }
            currentHeight = rung;
        }
        return rungsAdded;
    }
}
```
### Algorithm
- Initialize `rungsAdded = 0` and `currentHeight = 0`.
- For each `rung` in the `rungs` array:
  - Calculate the gap: `gap = rung - currentHeight`.
  - If `gap > dist`:
    - Calculate the number of rungs to add for this gap using the formula: `numToAdd = (gap - 1) / dist`.
    - Add this number to the total: `rungsAdded += numToAdd`.
  - Update `currentHeight = rung`.
- Return `rungsAdded`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
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))

```

### CPP

```cpp
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;
  }
};

```