[LeetCode 2411] Smallest Subarrays With Maximum Bitwise OR

문제 바로가기

Description

---

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 B_ij be the bitwise OR of the subarray nums[i...j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(B_ik) where i <= 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]
• Explanation:
  • The maximum possible bitwise OR starting at any index is 3.
    • Starting at index 0, the shortest subarray that yields it is [1,0,2].
    • Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
    • Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
    • Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
    • Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3]. Therefore, we return [3,3,2,2,1].

Example 2

---

• Input: nums = [1,2]
• Output: [2,1]
• Explanation:
  • Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
  • Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
  • Therefore, we return [2,1].

Constraints

---

• n == nums.length
• 1 <= n <= 10^5
• 0 <= nums[i] <= 10^9

Hint

---

Hint 1

  Consider trying to solve the problem for each bit position separately.
	

Hint 2

  For each bit position, find the position of the next number that has a 1 in that position, if any.
	

Hint 3

  Take the maximum distance to such a number, including the current number.
	

Hint 4

  Iterate backwards to achieve a linear complexity.
	

Code

---

내 제출

---

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int[] f = new int[32];
        Arrays.fill(f, -1);
        for (int i = n - 1; i >= 0; --i) {
            int t = 1;
            for (int j = 0; j < 32; ++j) {
                if (((nums[i] >> j) & 1) == 1) {
                    f[j] = i;
                } else if (f[j] != -1) {
                    t = Math.max(t, f[j] - i + 1);
                }
            }
            ans[i] = t;
        }
        return ans;
    }
}

Runtime	Memory
26 ms	61.9 MB

다른 풀이

---

class Solution {
    public int[] smallestSubarrays(int[] nums) {
         int n = nums.length;
        int[] ans = new int[nums.length];
        for (int i = 0; i < n; ++i)
        {
            int x = nums[i];
            ans[i] = 1;
            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; --j)
            {
                nums[j] |= x;
                ans[j] = i - j + 1;
            }
        }
        return ans;
    }
}

Reference

---

• https://github.com/doocs/leetcode/blob/main/solution/2400-2499/2411.Smallest%20Subarrays%20With%20Maximum%20Bitwise%20OR/Solution.java