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

mayankdv

Mayank Arora

Posted on December 24, 2021

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.

💖 💪 🙅 🚩
mayankdv
Mayank Arora

Posted on December 24, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related