Smallest Subarrays With Maximum Bitwise OR
01 · Problem
You are given an array nums of non-negative integers. For each index i, let best_i be the largest bitwise OR you can get from a non-empty subarray that starts at i (this is just the OR of nums[i..n-1]).
Return an array answer of the same length where answer[i] is the length of the shortest subarray starting at i whose bitwise OR equals best_i. A subarray always has length at least 1, so if best_i is 0 the answer is 1.
02 · Examples
nums = [4,0,1,2,4]
[4,4,3,2,1]
From index 0 the maximum OR is 7, which needs the bits of 4, 1 and 2, so [4,0,1,2] (length 4) is shortest. From index 1 you need [0,1,2,4] (length 4), from index 2 [1,2,4] (length 3), from index 3 [2,4] (length 2) and from index 4 just [4].
nums = [1,2]
[2,1]
From index 0 you need both elements to get OR 3. From index 1 the single element 2 is already the maximum.
nums = [0,0]
[1,1]
Every OR is 0, so the shortest subarray of length 1 already achieves the maximum.
03 · Constraints
- 011 <= nums.length <= 105
- 020 <= nums[i] <= 109
- 03The returned array has the same length as nums
04 · Optimal complexity
- Time
- O(n * 30)
- Space
- O(30)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.