BinarySearch 0748 Unique Numbers From Sublist Bitwise ORs

Problem statement

https://binarysearch.com/problems/Unique-Numbers-From-Sublist-Bitwise-ORs/

Solution

Equal to Leetcode 0898 Bitwise ORs of Subarrays.

Complexity

Time and space is O(n log W).

Code

class Solution:
    def solve(self, arr):
        @lru_cache(None)
        def dp(i):
            if i == 0: return tuple([arr[0]])
            return tuple(set(arr[i]|j for j in dp(i-1) + (0,)))
        
        return len({j for i in range(len(arr)) for j in dp(i)})