# Python 6 lines, bit by bit

• ``````def findMaximumXOR(self, nums):
for i in range(32)[::-1]:
prefixes = {num >> i for num in nums}
``````

Build the answer bit by bit from left to right. Let's say we already know the largest first seven bits we can create. How to find the largest first eight bits we can create? Well it's that maximal seven-bits prefix followed by 0 or 1. Append 0 and then try to create the 1 one (i.e., `answer ^ 1`) from two eight-bits prefixes from `nums`. If we can, then change that 0 to 1.

• Very elegant.

My attempt in CPP (how comes python gets a 389ms but cpp gets a 1062ms):

``````class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int res = 0;
unordered_set<int> pre;
for (int i = 31; i >= 0; i--) {
res <<= 1;
pre.clear();
for (auto n : nums)
pre.insert(n >> i);
for (auto p : pre)
if (pre.find((res ^ 1) ^ p) != pre.end()) {
res++;
break;
}
}
return res;
}
};
``````

• Vote +1.
Where could I find the definition about "range(32)[::-1]" in Python?
I am studying Python. But I can't find "list[::]" usage.
Thanks.

• @sevenduan It is same as `range(start=31, stop=-1, step=-1)`

• @sevenduan range(32) gives a list start from 0 to 31, then [::-1] reverses it.

a = [1, 2, 3, 4, 5]
a = a[::-1] #[5, 4, 3, 2, 1]

• @sevenduan It's called slicing, general form is `something_sliceable[start:stop:step]`, and all three parameters are optional. And you only need the second `:` if you provide a step. So for example `[:]` means no start and no stop, so the whole thing. And `[::-1]` means the whole thing, but backwards. Slices and slice notation are among the best things in Python, languages without them are stupid (IMHO).

I wrote it like that instead of the `range` that @ZheWang711 showed is that it's shorter and that I find it easier to read. Maybe I'm wrong about the latter :-)

• @shubin.xu.90

For reference, I got 119ms using C++ with a compressed trie approach. ;)

• What does `<<=` and `<<` mean?

I tried looking up on the web and textbook to understand the code but couldn't find any explanation. Sorry I am still learning!

Thanks!

• @keylessshackle Do you use STL? I think this should be the reason, but I'm not quite sure.

• @jeanie Logical shift.

1 << 2 becomes 0b100, equals 4.
4 >> 2 becomes 1.
<<= is quite same as += in function.

a = 1
a <<= 3 #a = 8 now

• @jeanie << is a bitwise operator and <<= sets the variable equal to the result after the operation is performed.
https://wiki.python.org/moin/BitwiseOperators

• @ZheWang711 It can interpreted as for(int i = 0; i < 32; i=i-1). i<32 => range(32) which is followed by [::-1] which is equivalent to i = i-1 or i--. if you want i++ you can do [::1]

• @htulipan Thank you!

• said in Python 6 lines, bit by bit:

def findMaximumXOR(self, nums):
for i in range(32)[::-1]:
prefixes = {num >> i for num in nums}

it seems of O(nlogn) complexity .

• @justin8 Note that n is the length of array, so it's will still be O(n). I guess you're probably thinking O(nlogm), if m is defined as maximum element in the array?

• said in Python 6 lines, bit by bit:

any(answer^1 ^ p in prefixes for p in prefixes)

wouldn't this step be O(n^2) since there actually exist two loops? As we could re-write it as:

``````for p in prefixes:
``````

• @CeltRay001 I don't think so. Prefixes is a set. To see if something exists or not in a set, it's a O(1) operation on average. Though https://wiki.python.org/moin/TimeComplexity says it can be O(n) in worst case...

• @preethikandhalu Yes u r right, I didn't notice its { }brackets

• This post is deleted!

• it took me almost two hours to figure out how these six lines' code work. It's really brilliant.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.