O(n) solution using buckets
The hints helped. What we\'re looking for is the lowest missing power of 2. This is because all other numbers can be created by the lower powers of two. 3 = 1 +
The hints helped. What we\'re looking for is the lowest missing power of 2. This is because all other numbers can be created by the lower powers of two. 3 = 1 + 2, 5 = 4 + 1, etc. This is more apparent when you make them into bits.\n\nSo the task becomes finding the smallest missing power of 2. If we use sort that makes it O(nlogn), so to avoid this just create and int[] bucket and then populate it with any power of 2 you find.\n\nThe smallest bucket that\'s empty (value of 0) is what you want. The anwer then is 2 ^ (smallest bucket)\n\n# Complexity\n- Time complexity:\nO(n)\n- Space complexity:\nO(1)\n\n# Code\n```\npublic class Solution {\n    public int MinImpossibleOR(int[] nums) {\n        int[] powers = new int[31];\n        \n        foreach(int num in nums) {\n            if(IsPowerOfTwo(num)) {\n                powers[(int)Math.Log(num, 2)]++;\n            }\n        }\n\n        for(int power = 0; power < powers.Length; power++) {\n            if(powers[power] == 0) {\n                return (int)Math.Pow(2 ,power);\n            }\n        }\n\n        return -1;\n    }\n\n    private bool IsPowerOfTwo(int x) {\n        return x > 0 && (x & (x - 1)) == 0;\n    }\n}\n```
['C#']