1562. XOR Spanning Cost
A power grid has one substation per entry of nums, and any two substations can be connected by a cable. The cost of a cable between substations i and j is the bitwise XOR nums[i] ^ nums[j]. Equal readings therefore connect for free.
Return the minimum total cost of cables needed so that every substation is reachable from every other one, as a long. With a single substation the answer is 0.
Checking every pair directly is wasteful for large inputs. The intended approach sorts the distinct values, splits them recursively on the highest bit where they differ, and joins the two halves with their cheapest cross XOR (found with a trie or a paired descent). Aim for roughly O(n * 30) time after sorting and O(n) extra space.
Example 1
- Input:
- nums = [1,2,3]
- Output:
- 3
- Explanation:
Cables 1-3 (cost 2) and 2-3 (cost 1) connect everything for a total of 3.
Example 2
- Input:
- nums = [5,5,5]
- Output:
- 0
- Explanation:
All readings are equal, so every cable is free.
Example 3
- Input:
- nums = [0,8,1,9]
- Output:
- 10
- Explanation:
Join 0-1 (1) and 8-9 (1), then bridge the pairs with 0-8 (8) for a total of 10.
Constraints
1 ≤ n ≤ 2000; 0 ≤ nums[i] ≤ 230 - 1; one node -> 0
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n + n * 30)
- Space
- O(n)