1936. Add Minimum Number of Rungs [Leetcode][C++]
Mayank Arora
Posted on December 24, 2021
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;
}
};
All suggestions are welcome. Please upvote if you like it. Thank you.
Posted on December 24, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.