898. Bitwise ORs of Subarrays

Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A subarray is a contiguous non-empty sequence of elements within an array.
 

Example 1:

Input: arr = [0]
Output: 1
Explanation: There is only one possible result: 0.

Example 2:

Input: arr = [1,1,2]
Output: 3
Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: arr = [1,2,4]
Output: 6
Explanation: The possible results are 1, 2, 3, 4, 6, and 7.

Constraints:

• $1<=arr.length<=5\ast 10^4$
• $0<=arr[i]<=10^9$

From: LeetCode
Link: 898. Bitwise ORs of Subarrays

Solution:

Ideas:

• Keep prev: all distinct ORs of subarrays ending at i-1 (≤ ~32 values).

• For each x = arr[i], form cur = {x} ∪ { (v | x) for v in prev }, deduped.

• Add every cur value to a global hash set to count distinct results.

• Each step adds at most ~32 new values, so total time is O(n * 32) and memory is manageable.

Code:

typedef struct {
    int *keys;
    unsigned char *used; // 0 = empty, 1 = occupied
    int cap_mask;        // cap - 1, cap is a power of two
    int size;
} IntHashSet;

static inline uint32_t mix32(uint32_t x) {
    x += 0x9e3779b9u;
    x ^= x >> 16;
    x *= 0x85ebca6bu;
    x ^= x >> 13;
    x *= 0xc2b2ae35u;
    x ^= x >> 16;
    return x;
}

static void hs_init(IntHashSet *hs, int capacity_pow2) {
    int cap = 1;
    while (cap < capacity_pow2) cap <<= 1;
    hs->keys = (int*)malloc(sizeof(int) * cap);
    hs->used = (unsigned char*)calloc(cap, 1);
    hs->cap_mask = cap - 1;
    hs->size = 0;
}

static int hs_insert(IntHashSet *hs, int key) {
    uint32_t h = mix32((uint32_t)key) & (uint32_t)hs->cap_mask;
    while (hs->used[h]) {
        if (hs->keys[h] == key) return 0; // already present
        h = (h + 1) & (uint32_t)hs->cap_mask;
    }
    hs->used[h] = 1;
    hs->keys[h] = key;
    hs->size++;
    return 1; // new key
}

static void hs_free(IntHashSet *hs) {
    free(hs->keys);
    free(hs->used);
}

int subarrayBitwiseORs(int* arr, int arrSize) {
    // Max distinct ORs overall is <= 32 * arrSize (~1.6e6 for worst case).
    // Use a hash set with capacity as a power of two comfortably larger than that.
    // 4,194,304 keeps load factor low.
    IntHashSet all;
    hs_init(&all, 1 << 22);

    int prev[64], prevLen = 0;
    int cur[64],  curLen  = 0;

    for (int i = 0; i < arrSize; ++i) {
        int x = arr[i];

        // Build the set of ORs for subarrays ending at i.
        curLen = 0;
        // Always include the single-element subarray [x]
        cur[curLen++] = x;

        // For each OR ending at i-1, OR with x to extend subarrays.
        for (int j = 0; j < prevLen; ++j) {
            int v = prev[j] | x;

            // Deduplicate within this small (<= ~32) list
            int seen = 0;
            for (int k = 0; k < curLen; ++k) {
                if (cur[k] == v) { seen = 1; break; }
            }
            if (!seen) cur[curLen++] = v;
        }

        // Insert into global set
        for (int k = 0; k < curLen; ++k) {
            hs_insert(&all, cur[k]);
        }

        // Prepare for next iteration
        memcpy(prev, cur, sizeof(int) * curLen);
        prevLen = curLen;
    }

    int ans = all.size;
    hs_free(&all);
    return ans;
}