O(n) time O(1) space C# explained
Intuition\nIt is impossible to generate a power of 2 by OR-ing together two other numbers. This is because a power of 2 only has a single 1-bit, and any other n
# Intuition\nIt is impossible to generate a power of 2 by OR-ing together two other numbers. This is because a power of 2 only has a single 1-bit, and any other number will have a 1-bit in some other location. So any OR involving another number will also have some other 1-bit and will not be equal to the original power of 2.  So if `nums` does not contain a given power of 2, then that power of 2 will be inexpressible. \n\nOn the other hand, if `nums` contains the first $$n$$ powers of 2, then we can easily generate any number less than the next power of 2 by selecting a subset of those powers of 2 to OR together.\n\nThis leads to the conclusion that the minimum impossible OR is simply the smallest power of 2 not contained in `nums`.\n\n# Approach\nThe simplest approach after reaching the above conclusion would be to add all the elements of `nums` into a set, and then iterate through powers of 2 checking if each one is in the set. However, it is a bit wasteful to store all the elements, since we only care about powers of 2. So we want to first check if the element is a power of two before storing it in the set. This could be done in log(nums[i]) time by comparing the element against each power, but there is a faster way. If x is a power of 2, then `x & (x-1)` will always be 0. E.g. if x=16, then in binary x is `10000` and x-1 is `01111`, so they share no bits and `x & (x-1) = 0`. Conversely, if `x` is not a power of 2, then `x & (x-1)` will not be 0, since x-1 will still contain the leftmost 1-bit in x. \n\nThe final optimization is that instead of using a literal set, we can recognize than an integer is essentially just a set of powers of 2, so we can can just use an int instead of a set. In order to add a power of 2 to the "set", we simply OR it into the integer.\n\nAfter iterating through `nums` and updating the set of powers of 2, all we have left is to find the first missing one, which we can do by iterating through increasing powers of 2 and checking if the corresponding bit is in the set.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```csharp []\npublic class Solution {\n    public int MinImpossibleOR(int[] nums) {\n        int pows = 0; // Used a set of powers of two present in nums\n        foreach(int x in nums) {\n            if ((x & (x-1)) == 0) { // x is a power of 2\n                pows |= x;\n            }\n        }\n        \n        int minpow = 1; \n        while((pows & minpow) > 0) { // minpow is present in nums\n            minpow = (minpow << 1);\n        }\n\n        return minpow;\n    }\n}\n```
['C#']