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.
Top comments (0)