FastPrepDistinct OR Values of Increasing Subsequences

Distinct OR Values of Increasing Subsequences

Scale AI logoScale AI● HardNEW GRADOA
Learn

Problem statement

The goodness of a sequence is the bitwise OR of all its elements. The empty sequence has goodness 0.

Given arr, consider every strictly increasing subsequence: chosen indices must preserve their original order, and each chosen value must be strictly larger than the previous chosen value.

Return every distinct goodness value in ascending order, including 0.

Function

distinctOrIncreasingSubsequences(arr: int[]) → int[]

Examples

Example 1

arr = [4,2,4,1]return = [0,1,2,4,6]

Distinct values come from the empty subsequence, singletons, and [2,4] with OR 6.

Example 2

arr = [3,2,4,6]return = [0,2,3,4,6,7]

For example, [3,4] contributes 7; duplicate scores are returned once.

Example 3

arr = [5,5,5]return = [0,5]

Equal values cannot follow one another in a strictly increasing subsequence.

Constraints

  • 1 <= arr.length <= 10000.
  • 1 <= arr[i] < 1024.

More Scale AI problems

See Scale AI hiring insights
public int[] distinctOrIncreasingSubsequences(int[] arr) {
    // write your code here
}
arr[4,2,4,1]
expected[0,1,2,4,6]
Checking account…