A player has to collect coins from various locations. The city is represented as a tree with n vertices labelled from 0 to n-1. There is an array called coins of size n where coins[i] is either 0 or 1, 1 means coin present and vice versa.
The player must travel along the tree to collect all the coins. The distance between two vertices is the edge connecting the points and if the player is at x then he can only collect coins that are located within distance of 2 edges of that vertex x.
The player can choose any vertex to start but then must end at that starting vertex only. All edges are bidirectional.
We need to return the number of edges in the shortest path such that all coins are collected.
Complete the function collectCoins in the editor.
collectCoins has the following parameters:
- 1.
int treeNodes: the number of vertices in the tree - 2.
vector: an array where each element is either&coins 0or1 - 3.
vector: an array representing one endpoint of an edge&tree_from - 4.
vector: an array representing the other endpoint of an edge&tree_to
Returns
int: the number of edges in the shortest path to collect all coins
treeNodes = 12 coins = [1,0,1,1,0,0,1,0,1,0,0,1] tree_from = [0,1 ,2,3,4,5,6,8,3,9,10] tree_to = [1,2,3,4,5,6,7,7,9,10,11] return = 10
- FizzBuzz ProblemSeen May 2025
- Find Largest Sum Contiguous SubarraySeen May 2025
- Find Largest Sum of Continuous SequenceSeen May 2025
- Find Palindrome Sub-stringSeen May 2025
- Flight Path Package DropSeen May 2025
- Count Numbers with Digit SumSeen Mar 2025
- Maximum Chocolates from Jars (L.C. 198 :)Seen Mar 2025
- Find Elements Largest in Row Smallest in ColumnSeen Mar 2025
public int collectCoins(int treeNodes, int[] coins, int[] tree_from, int[] tree_to) {
// write your code here
}