C++ | Sliding Window | Bit Manipulation
Intuition\n Describe your first thoughts on how to solve this problem. \nAs OR will always increase the value\nFor every index we find the maxOR value\nmaxOR va
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs OR will always increase the value\nFor every index we find the maxOR value\nmaxOR value at every index (i) is OR of every number from i to n\nThis can be done via sliding window and keeping a 30 bit array\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nNow we have maxOR value every index i can take\nWe use sliding window to find the lenght of the shortest window which can make maxOR value at index i\n\nThe 30 bit size vector is used to check that do we still have a contributing 1 in current window, if no then remove the set bit at this position\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> smallestSubarrays(vector<int>& nums) {\n        // or always increases value\n        int n=nums.size();\n        int currOr = 0;\n        vector<int> maxOr(n); // max OR value starting at index i\n        vector<int> v(32,0);\n        for(int i=0;i<n;i++){\n            for(int j=0;j<31;j++){\n                if(nums[i] & (1<<j)){\n                    v[j]++;\n                }\n            }\n            \n            currOr|=nums[i];\n        }\n\n\n        for(int i=0;i<n;i++){\n            maxOr[i] = currOr;\n            \n            for(int j=0;j<31;j++){\n                if(nums[i] & (1<<j)){\n                    v[j]--;\n                }\n                if(v[j]==0){\n                    currOr = (currOr & (~(1<<j)));\n                }\n            }\n        }\n\n        // sliding window to find smallest subarray size\n        currOr=0;\n        int j=0;\n        vector<int> ans(n);\n        vector<int> bit(32,0);\n        for(int i=0;i<n;i++){\n            while(currOr < maxOr[i]){\n                for(int k=0;k<31;k++){\n                    if(nums[j] & (1<<k)){\n                        bit[k]++;\n                    }\n                }\n                currOr|=nums[j];\n                j++;\n            }\n            ans[i] = j-i;\n            ans[i] = max(ans[i],1); //min value can be 1\n            for(int k=0;k<31;k++){\n                if(nums[i] & (1<<k)){\n                    bit[k]--;\n                }\n                if(bit[k]==0){\n                    currOr = (currOr & (~(1<<k)));\n                }\n            }\n            \n        }\n\n        return ans;\n    }\n};\n```
['Bit Manipulation', 'Sliding Window', 'C++']