|
| 1 | +# Time: O(nlogr * 2^n) |
| 2 | +# Space: O(2^n) |
| 3 | + |
| 4 | +# bitmasks, greedy |
| 5 | +classSolution(object): |
| 6 | +defmaximizeXorAndXor(self,nums): |
| 7 | +""" |
| 8 | + :type nums: List[int] |
| 9 | + :rtype: int |
| 10 | + """ |
| 11 | +defmax_xor_subset(nums):# Time: O(nlogr) |
| 12 | +base= [0]*l |
| 13 | +forxinnums:# gaussian elimination over GF(2) |
| 14 | +foriinreversed(xrange(len(base))): |
| 15 | +ifnotx&(1<<i): |
| 16 | +continue |
| 17 | +ifbase[i]==0: |
| 18 | +base[i]=x |
| 19 | +break |
| 20 | +x^=base[i] |
| 21 | +max_xor=0 |
| 22 | +forbinreversed(base):# greedy |
| 23 | +if (max_xor^b)>max_xor: |
| 24 | +max_xor^=b |
| 25 | +returnmax_xor |
| 26 | + |
| 27 | +l=max(nums).bit_length() |
| 28 | +n=len(nums) |
| 29 | +and_arr= [0]*(1<<n) |
| 30 | +xor_arr= [0]*(1<<n) |
| 31 | +formaskinxrange(1,1<<n): |
| 32 | +lb=mask&-mask |
| 33 | +i=lb.bit_length()-1 |
| 34 | +and_arr[mask]=and_arr[mask^lb]&nums[i]ifmask^lbelsenums[i] |
| 35 | +xor_arr[mask]=xor_arr[mask^lb]^nums[i] |
| 36 | +result=0 |
| 37 | +full_mask= (1<<n)-1 |
| 38 | +formaskinxrange(1,1<<n): |
| 39 | +total_and=and_arr[mask] |
| 40 | +total_xor=xor_arr[full_mask^mask] |
| 41 | +max_xor=max_xor_subset(((nums[i]&~total_xor)foriinxrange(n)ifnot (mask&(1<<i)))) |
| 42 | +result=max(result,total_and+total_xor+2*max_xor) |
| 43 | +returnresult |
| 44 | + |
| 45 | + |
| 46 | +# Time: O(nlogr * 2^n) |
| 47 | +# Space: O(1) |
| 48 | +# bitmasks, greedy |
| 49 | +classSolution2(object): |
| 50 | +defmaximizeXorAndXor(self,nums): |
| 51 | +""" |
| 52 | + :type nums: List[int] |
| 53 | + :rtype: int |
| 54 | + """ |
| 55 | +defmax_xor_subset(nums):# Time: O(nlogr) |
| 56 | +base= [0]*l |
| 57 | +forxinnums:# gaussian elimination over GF(2) |
| 58 | +foriinreversed(xrange(len(base))): |
| 59 | +ifnotx&(1<<i): |
| 60 | +continue |
| 61 | +ifbase[i]==0: |
| 62 | +base[i]=x |
| 63 | +break |
| 64 | +x^=base[i] |
| 65 | +max_xor=0 |
| 66 | +forbinreversed(base):# greedy |
| 67 | +if (max_xor^b)>max_xor: |
| 68 | +max_xor^=b |
| 69 | +returnmax_xor |
| 70 | + |
| 71 | +l=max(nums).bit_length() |
| 72 | +n=len(nums) |
| 73 | +result=0 |
| 74 | +formaskinxrange(1,1<<n): |
| 75 | +and_arr=-1 |
| 76 | +xor_arr=0 |
| 77 | +foriinxrange(n): |
| 78 | +ifmask&(1<<i): |
| 79 | +and_arr=and_arr&nums[i]ifand_arr!=-1elsenums[i] |
| 80 | +else: |
| 81 | +xor_arr^=nums[i] |
| 82 | +max_xor=max_xor_subset(((nums[i]&~xor_arr)foriinxrange(n)ifnot (mask&(1<<i)))) |
| 83 | +result=max(result,and_arr+xor_arr+2*max_xor) |
| 84 | +returnresult |