Interview Questions/Coding/Maximum Future OR Windows

Maximum Future OR Windows

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Maximum Future OR Windows

For every starting index in a telemetry array, consider all contiguous windows that begin at that index and extend to the right. The strongest possible bitwise OR from a starting index is the OR of the entire suffix beginning there. For each start, find the shortest window length whose bitwise OR already reaches that strongest suffix OR. Input Format: You are given an integer array readings. Output Format: Return an array answer where answer[i] is the minimum required window length starting at index i.

Examples

Example 1

Input:

readings = [1, 0, 2, 1, 3]

Output:

3 3 2 2 1

Explanation: start 0: OR target 3, length 3; start 1: OR target 3, length 3; start 2: OR target 3, length 2; start 3: OR target 3, length 2; start 4: OR target 3, length 1. Therefore the window lengths are 3 3 2 2 1.

Approach hint

Look for the state that actually matters after each operation.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp