Problem
The score of a subsequence is the bitwise OR of all its elements (the empty subsequence has score 0). Given an integer array arr, find every distinct score value achievable by a strictly increasing subsequence of arr, and return the values sorted in ascending order.
Input / Output
- Input:
int arr[n] — an array of integers.
- Output:
int[] — all possible distinct score values, sorted ascending.
Constraints
- 1 <= n <= 10^4
- 1 <= arr[i] <= 1024 (so every score fits below 2048)
- Subsequences must be strictly increasing in value while preserving index order.
Example
- arr = [3, 2, 4, 6] → [0, 2, 3, 4, 6, 7]. Singletons give 2, 3, 4, 6; [2,4] gives 2|4 = 6 and [3,4] gives 3|4 = 7. Longer chains like [2,4,6] (OR 6) and [3,4,6] (OR 7) add no new values, and 0 comes from the empty subsequence. Note [4, 2, 4, 1] → [0, 1, 2, 4, 6]: the second 4 can extend the earlier 2 (indices in order, values increasing), but the trailing 1 extends nothing.