# Leetcode 2568. Minimum Impossible OR
###### tags: `leetcode` `殘酷daily`

[題目連結](https://leetcode.com/problems/minimum-impossible-or/)

# Concept
:::warning
**Feature**

If `|nums[0] | nums[1] | ... | nums[n-1] | => x` can't gererate 0x7,
it means x lose 0x1 or 0x2 or 0x4.
so the the not expressible minimum positive non-zero integer is 0x1 or 0x2 or 0x4.
**Generally, the not expressible minimum positive non-zero integer is 2^p.
p maybe 0~31.**
:::

Following above feature,
let's think another conditions.
if `nums[0] = 5`, does it replace `0x1` and `0x4`.
the answer is `False`.

We can use variable to record the bitmap,
if the value is 2^p in nums, set the bit to bitmap.

scan the bitmap, if the bit`(p)` is 0,
we can say the not expressible minimum positive non-zero integer is 2^p

TC: O(32N) SC: O(1)
完整程式碼

class Solution {
public:
    int minImpossibleOR(vector<int>& nums) {
        int n = nums.size();
        int val = 0;
        int output = 0;
        //
        for(int a : nums) {
            for(int j = 0 ; j < 32 ; j++) {
                if(a == (1 << j)) {
                    val = val | a;
                    break;
                }
            }
        }

        for(int i = 0 ; i < 32 ; i++) {
            if((val & (1 << i)) == 0) {
                output = (1 << i);
                break;
            }
        }
        return output;
    }
};