Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1936.html

1936. Add Minimum Number of Rungs

Level

Medium

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.

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

Example 4:

Input: rungs = [5], dist = 10

Output: 0

Explanation:

This ladder can be climbed without adding additional rungs.

Constraints:

  • 1 <= rungs.length <= 10^5
  • 1 <= rungs[i] <= 10^9
  • 1 <= dist <= 10^9
  • rungs is strictly increasing.

Solution

The initial height is 0, which is the floor. Since rungs is strictly increasing, any two adjacent heights must be different. Each time calculate difference between two adjacent heights, and the minimum number of rungs needed between the two adjacent heights is (difference - 1) / dist. Finally, return the minimum total number of rungs needed.

  • class Solution {
    public int addRungs(int[] rungs, int dist) {
        int addCount = 0;
        int prev = 0;
        int length = rungs.length;
        for (int i = 0; i < length; i++) {
            int curr = rungs[i];
            int difference = curr - prev;
            addCount += (difference - 1) / dist;
            prev = curr;
        }
        return addCount;
    }
}

############

class Solution {
    public int addRungs(int[] rungs, int dist) {
        int res = 0;
        for (int i = 0, prev = 0; i < rungs.length; ++i) {
            res += (rungs[i] - prev - 1) / dist;
            prev = rungs[i];
        }
        return res;
    }
}

  • // OJ: https://leetcode.com/problems/add-minimum-number-of-rungs/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int addRungs(vector<int>& A, int d) {
        int prev = 0, ans = 0;
        for (int h : A) {
            if (prev + d < h) ans += (h - prev - 1) / d;
            prev = h;
        }
        return ans;
    }
};

  • class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        prev = res = 0
        for rung in rungs:
            res += (rung - prev - 1) // dist
            prev = rung
        return res

############

# 1936. Add Minimum Number of Rungs
# https://leetcode.com/problems/add-minimum-number-of-rungs/

class Solution:
    def addRungs(self, rungs: List[int], dist: int) -> int:
        prev = res = 0
        
        for rung in rungs:
            res += (rung - prev - 1) // dist
            prev = rung
        
        return res


  • 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
    }
}

All Problems

All Solutions