Linear time solution without binary search and additional space
Intuition\nFirstly i think how to reuse previous result. But starting from beginning gives only O(n^2) solution. Because i think about increasing sequnce of num
# Intuition\nFirstly i think how to reuse previous result. But starting from beginning gives only $$O(n^2)$$ solution. Because i think about increasing sequnce of numbers after applying OR operation. And using binary search was helped to find nearest max number.\n\nAfter that i gave time limit exceeded and began thinnking about improving. And finally i think to use sliding window and reach linear time. I noticed that last number is trivial case and we can move window from back to the beginning.\n\n# Approach\nI count bits count in each position of numbers added to sliding window. Function starts from trivial case when last number is max and subarray starts from last position. In each step sliding window moved left and right border reduced if needed. Solution populated from the end.\n\n# Complexity\n- Time complexity:\n$$O(n)$$ moving window is has linear time\n\n- Space complexity:\n$$O(1)$$ we just store answer (it\'s included?) and sliding window stores array of bits positions\n\n# Code\n```cpp []\n#include <vector>\n#include <array>\n#include <algorithm>\n\nstruct SlidingWindow {\n    std::array<int, 32> bit_count_in_pos{0};\n\n    // returns true if increase number\n    bool Add(int num) {\n        bool res = false;\n        int pos = 0;\n        while (num) {\n            if (num % 2) {\n                res |= bit_count_in_pos[pos] == 0;\n                ++bit_count_in_pos[pos];\n            }\n            ++pos;\n            num >>= 1;\n        }\n        return res;\n    }\n    \n    // returns true if we lost some bit\n    bool Delete(int num) {\n        bool res = false;\n        int pos = 0;\n        while (num) {\n            if (num % 2) {\n                --bit_count_in_pos[pos];\n                res |= bit_count_in_pos[pos] == 0;\n            }\n            ++pos;\n            num >>= 1;\n        }\n        return res;\n    }\n};\n\nclass Solution {\npublic:\n    std::vector<int> smallestSubarrays(std::vector<int>& nums) {\n        std::vector<int> res(nums.size());\n        res.back() = 1;\n        SlidingWindow sw;\n        sw.Add(nums.back());\n        int right_border = nums.size() - 1;\n        // we start from the end to dynamic programming approach\n        for (int left_border = nums.size() - 2; left_border >= 0; --left_border) {\n            sw.Add(nums[left_border]);\n            while (left_border < right_border) {\n                if (sw.Delete(nums[right_border])) {\n                    // don\'t move, we lost some bit\n                    sw.Add(nums[right_border]);\n                    break;\n                }\n                --right_border;\n            }\n            res[left_border] = right_border - left_border + 1;\n        }\n        return res;\n    }\n};\n```
['Dynamic Programming', 'Sliding Window', 'C++']