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

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

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