---
# System prepended metadata

title: Leetcode 2568. Minimum Impossible OR
tags: [leetcode, 殘酷daily]

---

# 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)
完整程式碼
```cpp=
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;
    }
};
```



