each I from 1 to k: track down such j (1≤j≤k, j≠i), for which (bi⊕bj) is the littlest among all such j, where ⊕ indicates the activity of bitwise XOR (https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Then, draw an undirected edge between vertices with numbers bi and bj in this chart.
Correct answer will be upvoted else Multiple Downvoted. Don't submit random answer. Computer science.
Think about a diagram on k hubs, with numbers from b1 to bk composed on them.
For each I from 1 to k: track down such j (1≤j≤k, j≠i), for which (bi⊕bj) is the littlest among all such j, where ⊕ indicates the activity of bitwise XOR (https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Then, draw an undirected edge between vertices with numbers bi and bj in this chart.
We say that the succession is acceptable if and provided that the subsequent diagram frames a tree (is associated and doesn't have any straightforward cycles).
It is conceivable that for certain numbers bi and bj, you will attempt to add the edge between them twice. All things considered, you will add this edge just a single time.
You can track down a model underneath (the image comparing to the main experiment).
Succession (0,1,5,2,6) isn't great as we can't arrive at 1 from 5.
Notwithstanding, grouping (0,1,5,2) is acceptable
You are given a succession (a1,a2,… ,an) of particular non-negative integers. You might want to eliminate a portion of the components (potentially none) to make the excess arrangement great. What is the base conceivable number of expulsions needed to accomplish this objective?
It tends to be shown that for any arrangement, we can eliminate some number of components, leaving something like 2, so the leftover grouping is acceptable.
Input
The main line contains a solitary integer n (2≤n≤200,000) — length of the grouping.
The subsequent line contains n unmistakable non-negative integers a1,a2,… ,an (0≤
Output
You should output precisely one integer — the base conceivable number of components to eliminate to make the excess grouping great
Step by step
Solved in 4 steps with 1 images
