Problem Statement
You have an important message that you need to share with all members of a group of friends. You will call one or more of them and relay the message. Those who have received the message can call additional members of your group of friends, until it has been heard by all.
You do not care how long it takes to spread the word; your only concern is the cost. Your phone company has assigned a "location code" to each of you, and the cost for one person to call another is based solely on their two location codes. The cost is computed as the square root of the XOR of the two codes. One caveat is that the call can only go through if there are at least three 1's in the binary representation of the XOR of the two codes.
For example, if two people's location codes are 263 and 943, the XOR of these is 680 (1010101000 in binary). Therefore, the cost for one of these people to call the other is the square root of 680, about 26.077. If two people's location codes are 263 and 15, the XOR of these codes is 264 (100001000 in binary) and they cannot communicate directly.
Given the location code for each member of a group of N friends (including yourself) as an int, locationCodes, compute the least expensive total cost to place the N-1 calls necessary to get the message to everyone. If it is not possible to get the message to everyone in the group, return -1. Your location code is given by the first element in locationCodes.
Definition
- Class:
- SpreadTheWord
- Method:
- totalCost
- Parameters:
- int[]
- Returns:
- double
- Method signature:
- double totalCost(int[] locationCodes)
- (be sure your method is public)
Notes
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- locationCodes will contain between 2 and 50 elements, inclusive.
- Each element of locationCodes will be between 0 and 10000, inclusive.
Examples
{ 263, 943, 15 }Returns: 56.53990204426623
This uses the examples from the problem statement. You (person 0) can call person 1 with a cost of about 26.077. You cannot call person 2, but person 1 can call person 2 with a cost of the square root of (943 XOR 15), about 30.463. The sum of these two costs is about 56.340.{ 574, 574 }Returns: -1.0
If two people have the same location code, they cannot call each other.{ 0, 28, 56, 7, 14 }Returns: 18.9320303488947
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }Returns: 28.305120873981032
{ 0, 0, 0, 25, 0 }Returns: 20.0
The only way to reach everyone is for you to call person 3, and for him to call everyone else. Four calls total, each at a cost of 5, results in a total cost of 20.
Back to all problems