Simple O(n) time, O(1) space
Intuition\n Describe your first thoughts on how to solve this problem. \nLogically, the OR function between two numbers can only be greater than or equal to the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLogically, the OR function between two numbers can only be greater than or equal to the largest input since it can change bits from 0 to 1, but never from 1 to 0. This also means that should there be any number that is not expressible with more than 1 "one bit," then turning one of the bit off would also be impossible to express. Therefore, the answer can have at most 1 "one bit." Since the answer cannot be 0, the answer must have exactly 1 "one bit." This means that the answer can be written in the form of 2<sup>n</sup>.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe only have a limited amount of solutions possible. Any possible solution that is inside the array cannot be the solution. By using the OR operation, we can concatenate impossible solutions.\nFor example, we are given the array [1, 2, 2, 3, 5, 8]\nThey come out to \n```\n0001 //<-Impossible Solution, literally expressed\n0010 //<-Impossible Solution, literally expressed\n0010 //<-Impossible Solution, literally expressed\n0011 //<-Can ignore because it is not 2^n\n0101 //<-Can ignore because it is not 2^n\n1000 //<-Impossible Solution, literally expressed\n```\n\nTaking only the removed solution, and applying the OR operation:\n```\n0001\n0010\n1000\n----\n1011\n```\nSee that 0 inside. That is the first position where it is impossible to express. The answer will be where that is the only bit active.\n\nSide note:\n`(num & (num - 1)) == 0` checks if a number is a power of 2 in O(1) time.\n`while((ans & temp) > 0) ans = ans << 1;` puts the 1 in the correct spot.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\nTechnicaly O(n + log(ans)) because it takes O(n) time to go through the entire array and O(log(ans)) time to put the 1 in the correct spot.\nHowever, log(ans) can be at most 1 more than the size of the array, and that only when the entire array is all possible solution (ex: [1, 2, 4, 8, 16, 32 ...])\nTherefore, we can drop the log(ans) and leave it at O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n) including the input array, O(1) excluding the input array.\n\n# Code\n```\nclass Solution {\n    public int minImpossibleOR(int[] nums) {\n        int temp = 0;\n        for(int num : nums) {\n            if ((num & (num - 1)) == 0) temp |= num;\n        }\n\n        int ans = 1;\n        while((ans & temp) > 0) ans = ans << 1;\n        return ans;\n    }\n}\n```
['Bit Manipulation', 'Java']