Shortest Subarray With OR at Least K I

Shortest Subarray With OR at Least K I

What is this problem about?

The Shortest Subarray With OR at Least K I interview question asks you to find the length of the shortest subarray of a non-negative integer array whose bitwise OR is at least K. If no such subarray exists, return -1. This is the easier version (EASY) where the array values are small enough for a brute-force approach to work within time limits.

Why is this asked in interviews?

Mitsogo asks this problem as an entry-level bitwise operation exercise. It tests knowledge of the bitwise OR operation's monotonic property: OR can only increase (or stay the same) as more elements are added to a window. This property enables sliding window or brute-force approaches. Understanding bitwise operations at the subarray level is foundational for harder bit-manipulation problems.

Algorithmic pattern used

The pattern is brute-force nested loop or sliding window. Nested loop: for each start index i, expand the subarray to the right computing running OR. Once the OR reaches or exceeds K, update the minimum length and break (adding more elements can't decrease the OR). This is O(n^2) but acceptable for small inputs. Alternatively, use a sliding window: since OR only grows, once OR ≥ K, try shrinking the left side. However, OR doesn't support efficient "undo" — track bit counts per position to enable shrinking.

Example explanation

Array: [2, 1, 8, 3], K = 10.

• Start i=0: OR starts at 2. i=0,j=1: OR=3. j=2: OR=11 ≥ 10 → length=3.
• Start i=1: OR=1. j=2: OR=9. j=3: OR=11 ≥ 10 → length=3.
• Start i=2: OR=8. j=3: OR=11 ≥ 10 → length=2. ✓
• Start i=3: OR=3 < 10.

Minimum length: 2 (subarray [8,3], OR=11).

Common mistakes candidates make

• Not terminating the inner loop once OR ≥ K — once found, further expansion only gives longer subarrays.
• Confusing OR with AND — bitwise OR only increases with more elements; AND can decrease.
• Returning 0 when K=0 — any empty OR is 0, but the problem likely requires at least one element.
• Not handling the "no valid subarray" case — if even the OR of the entire array < K, return -1.

Interview preparation tip

For the Shortest Subarray With OR at Least K I coding problem, the sliding window bit manipulation array interview pattern is the approach. The key property: OR is monotonically non-decreasing when adding elements — once a window's OR ≥ K, no extension of that window gives a shorter valid subarray with that starting index. Practice the "OR is monotone" insight — it's the same property that makes the harder version (Part II) tractable with a bit-count-based sliding window. Understanding this monotonicity is the gateway to all bitwise window problems.