[Python 3] [Binary Search] Solution with Intuition and Steps
\n### Intuitition:\nWhile applying bitwise OR on an array from the beginning to the end, once a bit is set to 1, it will not be set back to 0 anymore, as 1|?=1.
\n### Intuitition:\nWhile applying bitwise OR on an array from the beginning to the end, once a bit is set to 1, it will not be set back to 0 anymore, as `1|?=1`. \n\nTo find the smallest length array with maximum bitwise OR sum. we only need to find the first occurrence of the number since each index in the array with bit = 1 for each bit \n\n### Detailed Steps:\n- Limit in the problem indicates that each number n <= 10^9 which menas that n < 2^30 and there are at most 30 bits for numbers in the array.\n- For each bit, create a list to record the index of numbers in the array which has this bit equals to 1 `(n >> bit) % 2 == 1`. For example, for [0, 1, 3, 2], the index array for bit 0 is  [0, 2] and the index array for bit 1 is [2.3].  This step has `Complexity =  O(n * k)` where k = 30 in this problem.\n- For each index i in the number list, for each bit, find the first occurrence index of a number with this bit equals to 1. Put these occurrence index in the list IND. The smallest length array for index i is `max(IND) - i + 1`. For example,` for [1, 0, 3, 2], i = 1`, when i = 0, IND = [0, 2] and the result array should have `length = 2 - 0 + 1 = 3`, which is [1, 0, 3]. This step has` Complexity = O(nlogn * k)`\n\n\n### Solution:\n```\nclass Solution:\n    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n        maximum_bits = int(log(10**9, 2)) + 1\n        index_for_each_bit = [[] for _ in range(maximum_bits)]\n        # Create lists to record the index of numbers in the array with each bit = 1\n        for i in range(len(nums)):\n            n = nums[i]\n            for bit in range(maximum_bits):\n                if n % 2 == 1:\n                    index_for_each_bit[bit].append(i)\n                n >>= 1\n\n        res = []\n        for i in range(len(nums)):\n            cur_idx = [i]\n            n = nums[i]\n            # Find the first occurrence index of the number with each bit equals to 1\n            for bit in range(maximum_bits):\n                bit_index = index_for_each_bit[bit]\n                if n % 2 == 0:\n                    k = bisect_left(bit_index, i)\n                    if k < len(bit_index):\n                       cur_idx.append(bit_index[k])\n                n >>= 1\n            res.append(max(cur_idx) - i + 1)\n        return res\n```
['Binary Tree']