DEV Community 👩‍💻👨‍💻

Mayank Arora
Mayank Arora

Posted on

1936. Add Minimum Number of Rungs [Leetcode][C++]

All suggestions are welcome. Please upvote if you like it. Thank you.


Leetcode Problem Link: 1936. Add Minimum Number of Rungs


Input
rungs = [6,12,13,14,15], dist = 2
Output = 4

Ladder
---15
---14
---13
---12
---11
---10
---9
---8
---7
---6
---5
---4
---3
---2
---1
---0

Efficient Solution:
Concept of count1=(rungs[i]-rungs[i-1]-1)/dist vs count2=(rungs[i]-rungs[i-1])/dist

For example : If i=2, count1=(12-6)/2=3 & count2=(12-6-1)/2=2. From ladder diagram, if we add rungs at 8 & 10, it will enable us to climb from 6 to 12 in steps of 8-6=2=dist, 10-8=2=dist, 12-10=2=dist by adding minimum number of rungs. Hence, count2 is the correct equation.

class Solution {
public:
    int addRungs(vector<int>& rungs, int dist) {
        // Efficient Solution Time O(N) & Auxiliary Space O(1)
        int len=rungs.size();
        int count=(rungs[0]-1)/dist; 
        if(len==1)
            return count;
        for(int i=1;i<len;i++){
            count+=(rungs[i]-rungs[i-1]-1)/dist;
        }
      return count;
    }
};
Enter fullscreen mode Exit fullscreen mode

All suggestions are welcome. Please upvote if you like it. Thank you.

Top comments (0)

We are hiring! Do you want to be our Senior Platform Engineer? We're hiring for a Senior Platform Engineer and would love for you to apply.

Head here to learn more about who we're looking for.