Readme

2568.Minimum-Impossible-OR

解法1

有一道类似的经典题。给一个数组，求最小的自然数，使得它不是数组的任何subset的元素和。

我们将数组从小到大排列。假设前i-1个元素里，我们能构造连续的自然数[1,mx]，那么如果nums[i]<=mx+1，那么意味着前i个元素里，我们可以任意构造[1,mx+num[i]]里的元素。反之，如果nums[i]>mx+1，那么我们如论如何都无法构造出mx+1来。

同理，本题里的或运算和加法运算有着相同的性质：越搞数越大。假设前i-1个元素里，我们能构造连续的自然数[1,mx]，那么如果nums[i]<=mx+1，那么意味着前i个元素里，我们可以任意构造[1,mx|num[i]]里的元素。反之，如果nums[i]>mx+1，那么将nums[i]与任何[1,mx]里面的元素进行操作，得到的都会比nums[i]还大，我们如论也无法构造出mx+1来。

解法2

假设我们能够构造出2^0,2^1,..,2^k，那么意味着[1,2^(k+1)-1]里面的任何元素都能构造出来。但是我们肯定无法构造出2^(k+1)，所以我们只需要查看2^(k+1)是否在数组里即可。如果在的话，那么递归处理，我们只需要查看2^(k+2)是否在数组里即可。即本题求的就是最小的、不在数组里的2的幂。