0

Distinct OR values of increasing subsequences

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Distinct OR values of increasing subsequences

Companies: Scale AI

Difficulty: Medium

Problem statement

Given an integer array arr, define the goodness of a sequence as the bitwise OR of all its elements. The goodness of the empty sequence is 0.

A subsequence keeps elements in their original order but may skip any of them. Consider every strictly increasing subsequence of arr (each element is strictly greater than the one before it). The empty subsequence counts as strictly increasing.

Return every distinct goodness value that some strictly increasing subsequence can have, sorted in ascending order.

def distinct_goodness(arr: list[int]) -> list[int]: ...

Constraints

  • 0 <= len(arr) <= 10^4
  • 0 <= arr[i] < 1024

Example 1

arr = [2, 1, 4]
output = [0, 1, 2, 4, 5, 6]

The increasing subsequences are [], [2], [1], [4], [2, 4] and [1, 4], with goodness 0, 2, 1, 4, 6 and 5. [2, 1] is not increasing, so 3 is not reachable.

Example 2

arr = [3, 3, 3]
output = [0, 3]

Equal neighbours cannot both appear, so only [] and [3] count.

Approach

The goodness of a sequence is the bitwise OR of its elements, and the empty sequence has goodness 0. We need every distinct goodness value over all strictly increasing subsequences of arr, returned in ascending order.

Brute force. Enumerate all 2^n subsequences, keep the strictly increasing ones, and OR each one. That is O(2^n * n). It is fine for n up to about 15. It also makes a good oracle for testing, so write it first if the interviewer wants a baseline.

Quadratic DP over end positions. Let S[i] be the set of OR values of increasing subsequences that end at index i. Then S[i] = {arr[i]} ∪ { v | arr[i] : v in S[j], j < i, arr[j] < arr[i] }. Each set has at most 2^B values, where B is the bit width of the values. That gives O(n^2 * 2^B), which is too slow when n is 10^4.

Key observation: keep only the smallest last element per OR value. Two partial subsequences with the same OR value differ only in how they can be extended. A subsequence can be extended by a later element x exactly when its last element is less than x. So among all subsequences seen so far with OR value v, only the one with the smallest last element matters. Any extension the others allow, it also allows, and the extensions produce the same OR values.

So keep best[v] = the smallest last element of any increasing subsequence seen so far with OR equal to v. Start with best[0] = -infinity for the empty sequence. Then scan arr left to right. For each x, for every v with best[v] < x, set best[v | x] = min(best[v | x], x).

Updating in place is safe. During the step for x, every value we write is x itself. A state we just wrote has best = x, and x < x is false. So a state created in this step can never be extended by the same x in this step. That means we cannot reuse x by mistake, and we do not need to copy the table.

Invariant. After processing arr[0..i], best[v] is finite exactly when some strictly increasing subsequence of arr[0..i] has OR v, and then it equals the smallest possible last element among those subsequences (-inf for the empty sequence). The answer is every v with a finite best[v], in ascending order.

Size of the table. OR values never have more bits than the largest element. With M = max(arr) and B = M.bit_length(), there are at most 2^B states. If values are below 1024, that is 1024 states. In general, use a dict holding only the reachable values. The code below does that, so it also works when values are sparse.

Code

from itertools import combinations
from typing import Dict, List


def distinct_goodness_brute(arr: List[int]) -> List[int]:
    """O(2^n * n) oracle: try every subsequence."""
    seen = {0}
    n = len(arr)
    for k in range(1, n + 1):
        for idx in combinations(range(n), k):
            vals = [arr[i] for i in idx]
            if all(a < b for a, b in zip(vals, vals[1:])):
                acc = 0
                for v in vals:
                    acc |= v
                seen.add(acc)
    return sorted(seen)


def distinct_goodness(arr: List[int]) -> List[int]:
    """
    best[v] = smallest last element of an increasing subsequence with OR == v.
    The empty sequence has OR 0 and no last element (treated as -inf).
    """
    NEG_INF = float("-inf")
    best: Dict[int, float] = {0: NEG_INF}

    for x in arr:
        # Snapshot the keys: new states get best == x and can't take x again.
        for v, last in list(best.items()):
            if last < x:
                nv = v | x
                cur = best.get(nv)
                if cur is None or x < cur:
                    best[nv] = x

    return sorted(best)


if __name__ == "__main__":
    import random

    assert distinct_goodness([]) == [0]
    assert distinct_goodness([5]) == [0, 5]
    assert distinct_goodness([3, 3, 3]) == [0, 3]
    assert distinct_goodness([4, 2, 1]) == [0, 1, 2, 4]
    assert distinct_goodness([1, 2, 4]) == [0, 1, 2, 3, 4, 5, 6, 7]
    assert distinct_goodness([2, 1, 4]) == [0, 1, 2, 4, 5, 6]
    assert distinct_goodness([0, 0, 1]) == [0, 1]

    for _ in range(500):
        n = random.randint(0, 10)
        arr = [random.randint(0, 31) for _ in range(n)]
        assert distinct_goodness(arr) == distinct_goodness_brute(arr), arr
    print("ok")

Complexity

Let n = len(arr) and K be the number of reachable OR values. K is at most 2^B, where B is the bit length of max(arr).

  • Time: O(n * K). For n = 10^4 and values below 1024, that is about 10^7 simple steps. Sorting the answer adds O(K log K).
  • Space: O(K) for the best table, plus O(K) for the snapshot taken each step. With a fixed-size array of length 2^B you can skip the snapshot (see the in-place argument above).

Test cases

  • [] → [0] (only the empty sequence).
  • [5] → [0, 5].
  • [3, 3, 3] → [0, 3]. Equal values cannot follow each other, so 3 is never combined with itself (it wouldn't change the OR anyway).
  • [4, 2, 1] → [0, 1, 2, 4]. The array is decreasing, so only single elements and the empty sequence count.
  • [1, 2, 4] → [0, 1, 2, 3, 4, 5, 6, 7]. Every subset is increasing.
  • [2, 1, 4] → [0, 1, 2, 4, 5, 6]. 2 | 1 = 3 is missing because 1 comes after 2 and is smaller.
  • [0, 0, 1] → [0, 1]. Zeros add nothing.
  • [6, 1, 2] → [0, 1, 2, 3, 6]. [1, 2] gives 3. 6 cannot be followed by anything.
  • Large case: n = 10^4 with random values below 1024 runs in well under a second.

Follow-ups

  1. Return only the count, or the maximum goodness. Same DP. Return len(best) or max(best). For the maximum alone you still need the DP, because the OR of all elements may not be reachable by an increasing subsequence.
  2. Non-decreasing instead of strictly increasing. Change the test to last <= x. Now a state created by x could be extended by the same x in the same step. That is harmless for OR (v | x | x == v | x) and its best stays x, so in-place updates still work.
  3. Count how many subsequences produce each goodness value. The "smallest last element" shortcut no longer works, because every subsequence counts. Use cnt[x][v] = number of increasing subsequences ending with value x and OR v. Process elements in order and query the sum over all values below x with a Fenwick tree per OR value, or a Fenwick tree indexed by value whose nodes are arrays of size 2^B. That costs O(n * 2^B * log M). Take results modulo a prime.
  4. Values up to 10^9 but few distinct OR results. The dict version already scales with reachable states, not with 2^30. Mention that K can still blow up in the worst case (up to about 2^30), so ask for constraints. If K is large, a bitset over values is the next step.
  5. Answer queries on subarrays arr[l..r]. Offline, sort queries by l and run the DP from each distinct l. Or precompute for each start. Discuss the O(n^2 * K) cost and when it is acceptable.

Interviewer expectations

Mid-level (L4)

  • Restates the problem with the empty sequence included (answer always contains 0).
  • Writes the brute force or the O(n^2 * K) DP correctly.
  • Gets to the "keep the smallest last element per OR value" idea with a hint.

Senior (L5)

  • Finds the dominance argument without help and explains why one state per OR value is enough.
  • Notices the in-place update is safe because of strict inequality, or copies the table deliberately.
  • States the bound on states from the bit width and gives O(n * 2^B).
  • Tests against a brute-force oracle on small random inputs.

Staff (L6+)

  • Asks about constraints first (n, value range) and picks array vs. dict on purpose.
  • Handles follow-ups cleanly: non-decreasing, counting with Fenwick trees, large value ranges.
  • Explains clearly when the dominance trick breaks (counting) and why.

Sign in to comment, vote or remix.