Given a set of unsigned integers. How can I find the bit-permutation so that the maximum number is minimal?
I think the solution to the simpler problem in this thread is: Create a zero-initialized data structure of same size as original set, fill in columns from left (MSB) to right. Eagerly always pick the column that increases max the least.
-
-
I think you can use a similar structure to prune your search space in problem 2? Maybe an important fact: each column cannot reduce difference by more than weight of previous column (since (n-0)-(0-n)==2n) Maybe just DFS and pruning definitely-worse solutions is enough?
-
Doh, it's min of max not max of max. Still feels like po2 structure of integers and the fact difference is defined over two numbers gives some bounds you can exploit. Depends how fast it needs to be
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.