Remove a weight so the rest can't be balanced

Question

This code-golf challenge is based on the following puzzle:

You have an odd number of tokens whose weights are known whole numbers, and they don't all have the same weight. Show that there's a token you can remove so that the remaining tokens can't be split into two equal-size sets that have the same total weight.

Here's the canonical solution to the puzzle, which also suggests an algorithm to do it (spoilers if you want to solve the puzzle yourself):

If all the weights are even or all odd, the problem is unchanged if we truncate the least significant bit from each one (i.e. floor-divide by 2). Keep doing that until there's at least one even weight and one odd weight -- this must happen eventually because the total weight decreases at each step. Then, remove a weight whose parity is opposite the parity of the sum, leaving an odd total weight, which clearly prevents an even split.

Your goal is to figure out such a weight to remove. Shortest code wins.

Input:

An odd-size list of positive whole numbers, not all the same. Any list-like structure is fine, though it has to work with the numbers in any order.

Output:

One of those numbers, such that the remaining numbers can't be partitioned into two sets with equal size and equal sum. You must output the number, not its index.

If there's multiple choices, any one of them is fine. It doesn't have to be the number chosen by the solution above.

Your code should be able to handle test cases like below within one second.

Test cases:

[1, 2, 3]
1

[3, 3, 3, 3, 3, 3, 5]
3

[1, 2, 3, 4, 5, 6, 7, 8, 9]
2

[1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
1

[128, 256, 256]
256

[18770, 10578, 7506, 5458, 4434, 6482, 5458, 4434, 2386, 11602, 1362, 16722, 11602, 23890, 12626, 47442, 57682, 35154, 57682, 81234, 44370, 12626, 12626, 46418, 68946, 91474, 2386, 43346, 46418, 35154, 32082]
7506

If you want to see all possible outputs (this is just to show, your code must output exactly one):

[1, 2, 3]
{1, 2, 3}

[3, 3, 3, 3, 3, 3, 5]
{3}

[1, 2, 3, 4, 5, 6, 7, 8, 9]
{2, 4, 6, 8}

[1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
{1}

[128, 256, 256]
{256}

[18770, 10578, 7506, 5458, 4434, 6482, 5458, 4434, 2386, 11602, 1362, 16722, 11602, 23890, 12626, 47442, 57682, 35154, 57682, 81234, 44370, 12626, 12626, 46418, 68946, 91474, 2386, 43346, 46418, 35154, 32082]
{68946, 5458, 44370, 46418, 11602, 23890, 7506, 91474, 32082, 1362, 81234}

Answer 1

CJam, 19 17

q~:T{T:^^2bW%}$W=

Input format:

[1 2 3 4 5 6 7 8 9]

2 bytes thanks to Optimizer.

Answer 2

Python 2, 99

This came out pretty badly.

s=input()
b=1
while{x&b for x in s}<{0,b}:b+=b
print[x for x in s if(reduce(int.__xor__,s)^x)&b][0]

Numbers may be input comma-delimited.