Explained two solutions - With & Without extra space || Very Simple & Easy To Understand
Up vote if you like the solution !!!\n\n# Approach\n\nTrick : We just need to check if the 2\'s power are present in the array or not. \n\nWhy so ? \n\nlet\'s o
Up vote if you like the solution !!!\n\n# Approach\n\nTrick : We just need to check if the 2\'s power are present in the array or not. \n\nWhy so ? \n\nlet\'s observe few example :\n5 (101) is only possible if we have  100 + 1, that is 4 & 1 present\n6 (110) is only possible if we have  100 + 10, that is 4 & 2 present\nWe can see that, the number is possible if all 2\'s power lower to it present then its possible. \n\n1,2 present then 1- 3 any number possible\n1,2,4 present then 1 - 7 any number can be possible\n1,2,4,8 present then 1-15 any number can be possible\n\nIn other word only 2\'s power are not possible to form unless it is present in the array.\nSo we look for the smallest 2\'s power that is not present in the array, ans return it as answer.\n\nThis can be done in multiple ways. \nHere I have added two solutions one is space optimized and other one is time optimized.\n\n\n# Solution 1: with sorting & without extra space\n```\nclass Solution {\npublic:\n    int minImpossibleOR(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int n = 1;\n        for(int i = 0; i < nums.size(); ++i){\n            if(nums[i] > n) return n;\n            if(nums[i] == n) { n = n*2; }\n        }\n        return n;\n    }\n};\n```\n\n# Solution 2: with extra space and no sorting\n```\nclass Solution {\npublic:\n    int minImpossibleOR(vector<int>& nums) {\n        unordered_set<int> s(nums.begin(), nums.end());\n        int ans = 1;\n        while(s.find(ans) != s.end()){\n            ans = ans * 2;\n        }\n        return ans;\n    }\n};\n```\n\n# Solution 3: with out sorting & without any extra space\n\nHere basically we keep track of each bit of a number to check if a particular power of 2 is present or not.\nThis needs a good understanding of bit manupulation concept, if you don\'t have then try looking for the following :\n1. (n & (n - 1 )) to check if n is power of 2 or not \n2. bitwise NOT (one\'s complement) => ~n\n3. n &(-n) will give you value of n with  setting only first bit \'1\' in binary form of n. For example: n = 144 (0b10010000) => n&(-n) = 0b10000\n\n```\nclass Solution {\npublic:\n    int minImpossibleOR(vector<int>& nums) {\n        int cummRes = 0;\n        for (auto &n : nums) {\n            if ((n & (n-1)) == 0) cummRes |= n;  // check if number is power of 2\n        }\n        cummRes = ~cummRes; // identify the bit first lsb which is set to 0\n        return (cummRes & (-cummRes));  //return 2 power the bit no.\n    }\n};\n```\n\nHere is an article of my recent interview experience - A Journey to FAANG Company, I recomand you to go through this to know which all resources I have used & how I cracked interview at Amazon:\nhttps://leetcode.com/discuss/interview-experience/3171859/Journey-to-a-FAANG-Company-Amazon-or-SDE2-(L5)-or-Bangalore-or-Oct-2022-Accepted\n
['C++']