Snowflake
Online AssessmentDistinct Score Values
A coding competition organized to recruit software developers includes an operation.
The score of a sequence is defined as the result of the bitwise-OR operation on all elements of the sequence.
Given an array arr of length n, identify all possible distinct scores that can be obtained from any strictly increasing subsequence from the array. Return the results sorted in ascending order.
Note:
• An empty subsequence is valid and yields a score of 0.
• A subsequence is strictly increasing if each element is strictly greater than the preceding element.
- ▸The first line contains an integer n, the number of elements in arr.
- ▸The next n lines each contain an integer denoting arr[i].
- ▸Print all distinct score values sorted in ascending order, each on a new line (or return an array of integers sorted in ascending order).
- 1 <= n <= 10^4
- 1 <= arr[i] < 1024
4 4 2 4 1
0 1 2 4 6
Strictly increasing subsequences:
• Empty subsequence: score = 0
• [1]: score = 1
• [2]: score = 2
• [4]: score = 4
• [2, 4]: score = 2 | 4 = 6
Sorted distinct scores: [0, 1, 2, 4, 6].
4 3 2 4 6
0 2 3 4 6 7
Strictly increasing subsequences include empty (0), [2] (2), [3] (3), [4] (4), [6] (6), [2,4] (6), [3,4] (7), [3,6] (7), [3,4,6] (7), etc. Distinct scores: [0, 2, 3, 4, 6, 7].
Maintain reachable bitwise-OR scores for subsequences ending at each element value. Use a Binary Indexed Tree (Fenwick tree) over values 1..1024 to query the union of all reachable scores ending at elements smaller than arr[i] in O(log M) time.