Weather Mast Calibration Links
Minimum total cost to connect array elements with XOR-weighted edges
A weather station operates several sensor masts. Mast i has an integer calibration fingerprint fingerprints[i].
You may install a bidirectional calibration link between any two distinct masts. The cost of linking masts i and j is:
fingerprints[i] XOR fingerprints[j]
Here, XOR means bitwise exclusive OR.
Choose exactly n - 1 links so that every mast can reach every other mast through the installed links, where n is the number of masts. Return the minimum possible total link cost.
Masts with equal fingerprints are still distinct masts, and a link between them costs zero. For a single mast, no links are needed and the total cost is zero.
Examples
Example 1
Input: fingerprints = [3,7,6] Output: 5
The masts with fingerprints 7 and 6 are inexpensive to connect. The mast with fingerprint 3 can then be attached through whichever of those two masts gives the cheaper link.
Example 2
Input: fingerprints = [8,8,11,10] Output: 3
The two masts with fingerprint 8 can be joined for free. The remaining masts must still be connected to that pair, and choosing links independently by mast is not sufficient to guarantee a connected network.
Example 3
Input: fingerprints = [0] Output: 0
There is only one mast, so the network is already connected without installing a link.
Constraints
- 1 <= fingerprints.length <= 7000
- 0 <= fingerprints[i] <= 65535
- All link costs and the returned total are integers.
Let B = 16 and let u be the number of distinct fingerprints. The intended solution takes O(nB + uB^2) time and O(uB) auxiliary space. Equal fingerprints can be collapsed because all additional copies can be attached for zero cost. At a trie split, every cross-link is more expensive than every link within either child. The minimum spanning-tree cut property therefore supports solving both children independently and adding their cheapest bridge.
Hints
Show hint 1Hint 1
Organize the fingerprints in a binary trie, starting with their most significant bit. What distinguishes links inside one child subtree from links between the two children?
Show hint 2Hint 2
At each branching node, connect the two child networks using their cheapest possible cross-link. Find that link by querying one child trie with the fingerprints from the smaller child.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return an actual optimal set of links while keeping the original mast indices, including duplicate fingerprints?
- How would the running time and storage change if fingerprints could use up to 30 bits?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem