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

#cpp #algorithms #leetcode #programming

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