### niranjan_kumar's blog

By niranjan_kumar, history, 3 years ago,

Today, there was a test conducted by Uber and it's time slot was 8 AM to 2 PM (IST), so it has finished now. I need help in understanding the answer to a sample case of one of the problem. Problem was something like this:

There are N cities with a road between every pair of cities. Calculate the number of ways (modulo 1e9+7) such that you start travelling from city 1 and return to the same city 1 after completing exactly K trips where one trip means travelling from a current city to any other city.

Constraints: N <= 1e9; K <= 1e6

My approach: We start with city 1, now we have option to go (N-1) cities for 1st trip, then again (N-1) for 2nd trip, and so on. Hence, in short we have options of (N-1) cities for first (K-2) trips, then for the 2nd last trip we can go to (N-2) cities and for the last trip we have only 1 option that is to return to city 1. Hence according to this, answer should be: (N-1)^(K-2) * (N-2)

Sample Case: N=4, K=4

With my approach I am getting answer as 18. But according to author the answer should be 21. I need your help in understanding how there are 21 ways. I am not getting answer as 21 even when I try to find the ways using a pen and paper.

• 0

By niranjan_kumar, history, 4 years ago,

Recently, I got this message on Hackerearth. HACKEREARTH! Like LOL?!!

• -25

By niranjan_kumar, history, 4 years ago,

I have been thinking of learning Trie data structure, mainly for interview purposes but haven't found very good sources for it. If anyone can recommend some good tutorials (easy to understand) for trie it would be really helpful. Thanks in advance.

• +4