Smallest Subarrays With Maximum Bitwise OR
You are given a 0-indexed array nums of length n, consisting of non-negative integers. For each index i from 0 to n - 1, you must determine the size of the minimum sized non-empty subarray of nums starting at i (inclusive) that has the maximum possible bitwise OR.
- In other words, let
Bijbe the bitwise OR of the subarraynums[i...j]. You need to find the smallest subarray starting ati, such that the bitwise OR of this subarray is equal tomax(Bik)wherei <= k <= n - 1.
The bitwise OR of an array is the bitwise OR of all the numbers in it.
Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1
Input
nums = [1,0,2,1,3]Output
[3,3,2,2,1]The maximum possible bitwise OR starting at any index is 3, and the shortest subarray lengths achieving it from indices 0 through 4 are 3, 3, 2, 2, and 1.
Example 2
Input
nums = [1,2]Output
[2,1]Starting at index 0, the shortest subarray that yields the maximum bitwise OR has length 2, and starting at index 1 it has length 1.
Constraints
- n == nums.length
- 1 <= n <= 10^5
- 0 <= nums[i] <= 10^9