We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Add Minimum Number of Rungs

Difficulty: Medium

Problem 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 can only climb to the next highest rung if the distance between where you are currently at 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.

Key Insights

  • You start at height 0 and need to reach the first rung.
  • The distance between rungs must not exceed dist for you to climb without adding rungs.
  • By calculating the difference between consecutive rungs, we can determine how many additional rungs are required.
  • The total number of added rungs can be calculated by checking the gaps between the current position and the next rung.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we will iterate through the rungs array while keeping track of the current position on the ladder. Starting from the ground (height 0), we will check the height of each rung in the array. If the distance to the next rung exceeds dist, we need to calculate how many additional rungs are needed to make the climb possible. We can do this by determining the gap and dividing it by dist, adjusting for any remaining distance. Finally, we return the total number of rungs added.

Code Solutions

def addRungs(rungs, dist):
    # Initialize the number of rungs added and the current position
    added_rungs = 0
    current_position = 0
    
    for rung in rungs:
        # Calculate the gap between the current position and the next rung
        gap = rung - current_position
        
        # If the gap is greater than dist, we need to add rungs
        if gap > dist:
            # Calculate how many rungs are needed
            added_rungs += (gap - 1) // dist  # Use (gap - 1) to ensure we cover all distance
        # Move to the next rung
        current_position = rung
    
    return added_rungs
← Back to All Questions