c++ code for those who are struggling class Solution { public: long long result=0; int dfs(int node,int parent,unordered_map&adj,int seats) { int passengers=0; for(auto &x:adj[node]) { if(x!=parent) { int p=dfs(x,node,adj,seats); passengers+=p; result+=(int)ceil(p*1.0/seats); } } return passengers+1; } long long minimumFuelCost(vector& roads, int seats) { unordered_mapadj; for(auto &x:roads) { adj[x[0]].push_back(x[1]); adj[x[1]].push_back(x[0]); } dfs(0,-1,adj,seats); return result; } };
@Puja Kumari In case we simply use (p / seats), C++ will perform integral division (divide and round down) and return a rounded down integer (which will lead to a wrong answer). p * 1.0 will result in a double type and further divide it will give us the correct result. Hope this help !
@@PujaKumari-zl7rw wo example dekho like usme at node 2 we have passengers=3 to be moved from node 2 to 0 and har car me 2 seat hai we have 3 nodes to be moved so we need 2 cars right so we use ceil(p/seats ) and 1.0 for floating value to convert into int value since ceil deals with floating values if we do direct 3/2 here ans is 1 right so 3*1.0/2 lagane se we get ceil(1.5)=2
Why a second channel when you could have posted this from your main account and add it to the existing graph playlist making it 1 stop solution for all neetcode graph problems ?
not cleared about something 1st: we are going from bottom to the root nodes right or from root to bottom 2nd: what's the use of passenger+1 , '+1' didn't understand
I could not understand this, let's take the example at @7:26 , why is it 4 fuel to reach from node 2 to 0? can we not take a car which has 5 seats and take all the 3 people at node 2 so only 1 fuel from there onwards.
Stuck with this for today challenge. Thank you for a detail explanation
I solved the question without seeing any solution and with your idea until 6:10 of the video. Thanks for the great explanation.
Thank you , this solution seems so easy when you code it up.
So clear and concise, thx dude
c++ code for those who are struggling
class Solution {
public:
long long result=0;
int dfs(int node,int parent,unordered_map&adj,int seats)
{
int passengers=0;
for(auto &x:adj[node])
{
if(x!=parent)
{
int p=dfs(x,node,adj,seats);
passengers+=p;
result+=(int)ceil(p*1.0/seats);
}
}
return passengers+1;
}
long long minimumFuelCost(vector& roads, int seats) {
unordered_mapadj;
for(auto &x:roads)
{
adj[x[0]].push_back(x[1]);
adj[x[1]].push_back(x[0]);
}
dfs(0,-1,adj,seats);
return result;
}
};
Hi, Can you tell me why do we need (p*1.0/seats) above?
@Puja Kumari In case we simply use (p / seats), C++ will perform integral division (divide and round down) and return a rounded down integer (which will lead to a wrong answer).
p * 1.0 will result in a double type and further divide it will give us the correct result.
Hope this help !
@@PujaKumari-zl7rw wo example dekho like usme at node 2 we have passengers=3 to be moved from node 2 to 0 and har car me 2 seat hai we have 3 nodes to be moved
so we need 2 cars right
so we use ceil(p/seats ) and 1.0 for floating value to convert into int value since ceil deals with floating values
if we do direct 3/2 here ans is 1 right so 3*1.0/2 lagane se we get ceil(1.5)=2
DFS solution is much nicer for this problem compared to BFS (which is doable but slightly harder to write)
7:50 shouldn't space complexity be O(N) since we are building an adjacency list?
Bro, I really wish you can fill all LC questions one day lol.
I originally misread it to think that each car had a different capacity. That would have been an interesting problem.
Just amazing explanation
This was a really nice problem
why does the dfs call return the number of current passengers?
Awesome explanation
best explanation
0:12 hmm🧐
😳
XD
That was fast!
What if each city has car with variable seat basically we are given list of seats?
Why a second channel when you could have posted this from your main account and add it to the existing graph playlist making it 1 stop solution for all neetcode graph problems ?
He wants to make non-Leetcode solution related content in the future for his main channel
I can still add these videos to the playlists on the main channel, I'll prob do that and then link the playlists in the video descriptions
not cleared about something
1st: we are going from bottom to the root nodes right or from root to bottom
2nd: what's the use of passenger+1 , '+1'
didn't understand
we are going from root to bottom and passengers + 1 is needed to include the node itself to the passengers variable
I could not understand this, let's take the example at @7:26 , why is it 4 fuel to reach from node 2 to 0? can we not take a car which has 5 seats and take all the 3 people at node 2 so only 1 fuel from there onwards.