FastPrepFastPrep
Problem Brief

Collect Coins

OA

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.

Function Description

Complete the function collectCoins in the editor.

collectCoins has the following parameters:

  1. 1. int treeNodes: the number of vertices in the tree
  2. 2. vector &coins: an array where each element is either 0 or 1
  3. 3. vector &tree_from: an array representing one endpoint of an edge
  4. 4. vector &tree_to: an array representing the other endpoint of an edge

Returns

int: the number of edges in the shortest path to collect all coins

1Example 1

Input
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]
Output
10
Explanation
:)
public int collectCoins(int treeNodes, int[] coins, int[] tree_from, int[] tree_to) {
  // write your code here
}
Input

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]

Output

10

Sign in to submit your solution.