Frog Position After T Seconds Inmobi - IIT Hyderabad

Problem Preview

"**Mode:** On-Campus **Exam Pattern:** 3 dsa questions **OA Date:** 2026-10-09 # Frog Position After T Seconds You are given an undirected tree consisting of N nodes numbered from 1 to N. A frog starts at node 1. Every second, the frog jumps from its current node to an unvisited adjacent node. The frog cannot visit a previously visited node again. https://leetcode.com/problems/frog-position-after-t-seconds/description/ If there are multiple unvisited adjacent nodes, the frog chooses one randomly, with equal probability for each available node. If the frog has no unvisited adjacent nodes, it stays at its current node forever. You are given an integer T representing the number of seconds and an integer target representing the target node. Your task is to calculate the probability that the frog is at the target node after exactly T seconds. ## Input Format - The first line contains an integer N, representing the number of nodes. - The next N - 1 lines contain two integers u and v, representing an undirected edge between nodes u and v. - The next line contains two integers T and target, representing the time in seconds and the target node. ## Output Format Print the probability that the frog is at the target node after exactly T seconds. Answers with an absolute error of at most 10^-5 are accepted. ## Constraints - 1 ≤ N ≤ 100 - Number of edges = N - 1 - 1 ≤ T ≤ 50 - 1 ≤ target ≤ N ## Sample Input 1 ``` 7 1 2 1 3 1 7 2 4 2 6 3 5 2 4 ``` ## Sample Output 1 ``` 0.1666666667 ``` ## Explanation Initially, the frog is at node 1. - After 1 second, the frog can move to node 2, node 3, or node 7, each with probability 1/3. - To reach node 4, the frog must first move to node 2, with probability 1/3. - From node 2, it can move to node 4 or node 6, each with probability 1/2. Therefore, the probability of reaching node 4 after exactly 2 seconds is: Probability = (1/3) × (1/2) = 1/6 = 0.1666666667. ## Sample Input 2 ``` 7 1 2 1 3 1 7 2 4 2 6 3 5 1 7 ``` ## Sample Output 2 ``` 0.3333333333 ``` ## Explanation After 1 second, the frog can move from node 1 to nodes 2, 3, or 7 with equal probability. Therefore, the probability of being at node 7 after exactly 1 second is 1/3 = 0.3333333333."