We have an array A of non-negative integers.
For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].
Return the number of possible results.  (Results that occur more than once are only counted once in the final answer.)
 

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


Example 2:
Input: [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: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.




 
Note:

1 <= A.length <= 50000
0 <= A[i] <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res = set()
        cur = set()
        for a in A:
            cur = {a | i for i in cur}
            cur |= {a}
            res |= cur
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        s = set()
        c = set()
        for x in A:
            c = {x|y for y in c}
            c.add(x)
            s|=c
        return len(s)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = set([0])
        
        for x in A:
            cur = {x | y for y in cur} | {x}
            ans |= cur
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        prev = set()
        curr = set()
        vals = set(A)
        
        for x in A:
            curr.add(x)
            for y in prev:
                curr.add(x|y)
                vals.add(x|y)
            prev = curr
            curr = set()
        
        return len(vals)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        curr = set()
        ans = set()
        for x in A:
            curr = {x | y for y in curr} | {x}
            ans |= curr
        
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        results = set()
        curr = {0}
        for a in A:
            curr = {a | b for b in curr} | {a}
            results |= curr
        return len(results)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res, cur = set(), set()
        for i in A:
            cur = {i | j for j in cur} | {i}
            res |= cur
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # O(N^3) to try oring every possible subarray
        
        # key fact: for any number k , k | k = k
        # also 0 | k = k for all k
        
        # one small optimization: scan through and delete any 0s or consecutive repeats
        
        # keep a list of or results s.t. or[i] = set of all possible results from oring subarrays that end at i
        # then or[i] = [A[i]] + [A[i] | res for res in or[i - 1]] -> use a set to prune dups at each step
        #    you can just keep or[i] for most recent two i's
        # 
        if not A:
            return []
        # [1, 2, 4]
        # all_outcomes: {1, 2, 3, 4, 6, 7}
        # outcomes: {2, 3}
        # 4: temp {4, 6, 7}
        
        # todo(mywang): preprocess array and remove unnecessary stuff
        for i in range(len(A))[::-1]:
            if (i > 0 and A[i] == A[i - 1]):
                A.pop(i)
        all_outcomes = set([A[0]])
        outcomes = set([A[0]])
        for elt in A[1:]:
            outcomes = {elt} | {elt | val for val in outcomes}
            all_outcomes |= outcomes
        
        return len(all_outcomes)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans=set()
        cur=set()
        for i in A:
            cur = set([i|j for j in cur])
            cur.add(i)
            ans|=cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        cur = set()
        all = set()
        for v in A:
            cur = set(e | v for e in cur)
            cur.add(v)
            all |= cur
        return len(all)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = {0}
        for i in A:
            cur = {i | y for y in cur} | {i}
            ans |= cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        cur, res = set(), set()
        for i in A:
            cur = {i | j for j in cur} | {i}
            res |= cur
        return len(res)

import math
class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res = set([])
        tmp = []
        maximpact = 0
        for i in A:
            newtmp = []
            newtmp_set = set([])
            maximpact = max(maximpact, int(math.log(i, 2)) + 1 if i > 0 else 0)
            if i not in newtmp_set:
                newtmp_set.add(i)
                newtmp.append(i)
                res.add(i)
            if maximpact > 0:
                for j in tmp:
                    k = i|j
                    if k not in newtmp_set:
                        newtmp_set.add(k)
                        newtmp.append(k)
                    res.add(k)
                    if len(newtmp) >= maximpact:
                        break
            tmp = newtmp
        return len(res)
            
                
            


class Solution(object):
    def subarrayBitwiseORs(self, A):
        ans = set()
        cur = {0}
        for x in A:
            cur = {x | y for y in cur} | {x}
            ans |= cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        result, curr = set(), set()
        for a in A:
            curr = {a | j for j in curr} | {a}
            result |= curr
        return len(result)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        results = set()
        temp = {0}
        for cur in A:
           # print(temp)
            temp = {cur} | {cur | t for t in temp}
            results.update(temp)
        return len(results)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        s = set()
        global_set = set()
        ans = 0
        for v in A:
            s.add(v)
            s = {x|v for x in s}
            global_set |= s
            
        return len(global_set)

import math
class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = {A[0]}
        pre = {A[0]}
        for a in A[1:]:
            pre = {a|x for x in pre}
            pre.add(a)
            ans.update(pre) 
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        S, last = set(), set()
        for i in range(len(A)):
            last = {a|A[i] for a in last}
            last.add(A[i])
            S |= last
            
        return len(S)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = {0}
        for x in A:
            cur = {x | y for y in cur} | {x}
            ans |= cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        
        
        
        # my solution ... 760 ms ... 98 % ... 40.6 MB ... 15 %
        #  time: O(nlogn)
        # space: O(logn)
        
        res = set()
        tot = set()
        for a in A:
            res = {prev | a for prev in res} | {a}  # 得出以当前 a 结尾的 subarray
            tot |= res                              # 把结果并入 tot
        return len(tot)
        
        


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = set([0])
        
        for x in A:
            cur = set([x | y for y in cur]) | {x}
            ans |= cur
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        previous = set()
        for v in A:
            current = set([i|v for i in previous])
            current.add(v)
            ans.update(current)
            previous = current
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        st = set()
        cur = set()
        for a in A:
            cur = {b | a for b in cur} | {a}
            st |= cur
        return len(st)

from typing import List


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        seen = set()
        cur = set()

        for num in A:
            cur_new = set()
            for num_seen in cur:
                cur_new.add(num_seen | num)

            cur_new.add(num)
            cur = cur_new
            seen |= cur

        return len(seen)

    def subarrayBitwiseORsN2(self, A: List[int]) -> int:
        dp = [[0] * len(A) for _ in range(len(A))]

        seen = set()

        count = 0

        for start in reversed(list(range(len(A)))):
            for end in range(start, len(A)):
                if start == end:
                    dp[start][end] = A[start]
                else:
                    dp[start][end] = dp[start + 1][end] | A[start]

                if dp[start][end] not in seen:
                    count += 1
                    seen.add(dp[start][end])

        return count


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = {0}
        for x in A:
            cur = {x|y for y in cur} | {x}
            ans |= cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # Brute force with set, with list we can use if in list conditional statement
        # Slow & bad....

#        rset = set()
#        for i in range(len(A)):
#            for j in range(i+1, len(A)+1):
#                res = 0
#                for k in range(i, j):
#                    res |= A[k]
#                rset.add(res)
#        return len(rset) 
        
#        A cleaner code
#        Assume B[i][j] = A[i] | A[i+1] | ... | A[j]
#        Hash set cur stores all wise B[0][i], B[1][i], B[2][i], B[i][i].

#        When we handle the A[i+1], we want to update cur
#        So we need operate bitwise OR on all elements in cur.
#        Also we need to add A[i+1] to cur.

#        In each turn, we add all elements in cur to res.
# This method is better since it preserves the results of previous operation and make them useful
        res, cur = set(), set()
    
        for i in A:
            cur = {i|j for j in cur} | {i}
            res |= cur
        
        return len(res)
        


class Solution(object):
    def subarrayBitwiseORs(self, A):
        ans = set()
        cur = {0}
        for x in A:
            cur = {x | y for y in cur} | {x}
            ans|=cur
            #print(cur)
            #print(\"ans\",ans)
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        
        result = set()
        cur = {0}
        
        for x in A:
            cur = {x | y for y in cur} | {x}
            result |= cur
        
        return len(result)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        s = set()
        res = set()
        for x in A:
            new_s = {x}
            for xx in s:
                new_s.add(xx | x)
            s = new_s
            res |= s
        return len(res)

import itertools as it


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res, cur = set(), set()
        for i in A:
            cur = {i | j for j in cur} | {i}
            res |= cur
        return len(res)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        cur, res = set(), set()
        for a in A:
            cur = {a|b for b in cur} | {a}
            res |= cur
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        
        cur = {0}
        
        for x in A:
            cur = {x|y for y in cur} | {x}
            ans |= cur
        
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # 12:57 8/24/20
        
        cur, res = set(),set()
        for num in A:
            cur = {num | j for j in cur} | {num}
        #     res |= cur
            # cur = set(num | k for k in A)
            # cur.add(num)
            res.update(cur)
        
        return len(res)
        
        
                
        # res, cur = set(), set()
        # for i in A:
        #     cur = {i | j for j in cur} | {i}
        #     res |= cur
        # return len(res)

            
                


class Solution:
#     def findUnique(self, l):
#         u = []
        
#         for num in l:
#             if num not in u:
#                 u.append(num)
                
#         return self.findOR(u)
    
#     def findOR(self, l):
        
#         ret = 0
        
#         for num in l:
#             ret = self.doBin(ret, num)
#         return ret
    
    
#     def doBin(self, a, b):
        
#         p = 0
        
#         ret = 0
#         while a or b:
#             if a%2 or b%2:
#                ret += pow(2,p)
#             p +=1
#             a, b = a//2, b//2
        
#         return ret
    
#     def subarrayBitwiseORs(self, A: List[int]) -> int:
#         #just unique combinations
        
#         res = 0 
        
#         seen = []
#         #brute force
#         for i in range(len(A)):
#             for j in range(i,len(A)):
#                 uniq = self.findUnique(A[i:j+1])
#                 if uniq not in seen:
#                     seen.append(uniq)
#                     res +=1
                    
#         return res


    def subarrayBitwiseORs(self, A):
        ans = set()
        cur = {0}
        for x in A:
            cur = {x | y for y in cur} | {x}
            ans |= cur
        return len(ans)





class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        n = len(A)
        dp = set()
        ans = set()
        
        for j in range(n):
            dp_new = set()
            dp_new.add(A[j])
            for x in dp:
                dp_new.add(x | A[j])
            dp = dp_new 
            ans.update(dp)
                
        return len(ans)        


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans, dp = set(), set()
        for x in A:
            ndp = set()
            ndp.add(x)
            for y in dp:
                ndp.add(x|y)
                ans.add(y)
            dp = ndp
        for x in dp: ans.add(x)
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # O(N^3) to try oring every possible subarray
        
        # key fact: for any number k , k | k = k
        # also 0 | k = k for all k
        
        # one small optimization: scan through and delete any 0s or consecutive repeats
        
        # keep a list of or results s.t. or[i] = set of all possible results from oring subarrays that end at i
        # then or[i] = [A[i]] + [A[i] | res for res in or[i - 1]] -> use a set to prune dups at each step
        #    you can just keep or[i] for most recent two i's
        # 
        if not A:
            return []
        # [1, 2, 4]
        # all_outcomes: {1, 2, 3, 4, 6, 7}
        # outcomes: {2, 3}
        # 4: temp {4, 6, 7}
        
        # todo(mywang): preprocess array and remove unnecessary stuff
        for i in range(len(A))[::-1]:
            if (i > 0 and A[i] == A[i - 1]):
                A.pop(i)
        all_outcomes = set([A[0]])
        outcomes = set([A[0]])
        for elt in A[1:]:
            temp = set([elt])
            for out in outcomes:
                temp.add(out | elt)
            outcomes = temp
            all_outcomes |= outcomes
        
        return len(all_outcomes)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        tp = set()
        tp.add(0)
        for i in A:
            tpp = set()
            tpp.add(i)
            for ii in tp:
                tpp.add(ii|i)
            tp=tpp
            for ii in tp:
                ans.add(ii)
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        s = set()
        res = set()
        for n in A:
            s = {n} | {n | el for el in s}
            res |= s

        return len(res)

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        ans = set()
        current = set()
        current.add(0)
        for i in range(len(arr)):
            a = arr[i]
            s = set()
            s.add(a)
            for y in current:
                s.add(a | y)
            current = s
            ans |= s
        return len(ans)
    
        # for x in arr:
        #     current = {x | y for y in current} | {x}
        #     # print(current)
        #     ans |= current
        #     # print(ans)
        # return len(ans)
    
        # brute force time complexity :O(n^2)
        # space complexity:O(n)
        if not arr:return 0
        l ,ans = len(arr) ,set()
        for i in range(l):
            res = arr[i]
            ans.add(res)
            for j in range(i+1,l):
                res |= arr[j]
                ans.add(res)
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        fullSet = set()
        setAtI = {0}
        
        for i in range(len(A)):
            setAtI = {A[i]| y for y in setAtI} | {A[i]}
            fullSet |=setAtI
        return len(fullSet)
        
        


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        setA = set(A)
        
        prev = set()
        
        prev.add(A[0])
        
        for val in A[1:]:
            temp = set()
            
            for p in prev:
                temp.add(p|val)
                setA.add(p|val)
            prev = temp
            prev.add(val)
        return len(setA)

import math
class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = {A[0]}
        pre = {A[0]}
        for a in A[1:]:
            pre = {a|x for x in pre}
            pre.add(a)
            for i in pre:
                ans.add(i) 
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans=set()
        vset=set()
        for a in A:
            newvset=set()
            for v in vset:
                newvset.add(a|v)
                ans.add(a|v)
            newvset.add(a)
            vset=newvset
            ans.add(a)
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
 
        cur = set()
        res = set()
        for i in A:
            temp = set([i])
            for j in cur:
                temp.add(i|j)
            cur = temp
            for j in cur:
                res.add(j)
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        
        result, prev = set(), set()
        
        for num in A:
            temp = set()
            temp.add(num)
            
            result.add(num)
            
            for p in prev:
                temp.add(p|num)
                result.add(p|num)
            
            prev = temp
        return len(result)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        S, prev = set(), set()
        for a in A:
            temp = set()
            temp.add(a)
            S.add(a)
            for p in prev:
                temp.add(a|p)
                S.add(a|p)
            prev = temp
        return len(S)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        alive = set()
        dead = set()
        for num1 in A:
            tmp = {num1}
            for num2 in alive:
                dead.add(num2)
                tmp.add(num1|num2)
            alive = tmp
            
        return len(alive|dead)

class Solution:
    
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        arr_len = len(A)
        final_result_set = set()
        pre_result_set = set()
        pre_result_set.add(A[0])
        final_result_set.add(A[0])
        for i in range (1, arr_len):
            cur_result_set = set()
            for pre_result in pre_result_set:
                one_cur_result = pre_result | A[i]
                cur_result_set.add(one_cur_result)
                final_result_set.add(one_cur_result)
            cur_result_set.add(A[i])
            final_result_set.add(A[i])
            pre_result_set = cur_result_set
        return len(final_result_set)
            
                    
                    
        


class Solution:
    def subarrayBitwiseORs(self, A):
        nums, n, pre = set(), len(A), set()
        for a in A:
            pre = {a} | {num | a for num in pre}
            nums |= pre
        return len(nums)

# @param {Integer[]} a
# @return {Integer}
#def subarray_bitwise_o_rs(a)
    # Get subarrays
#    solutions = {}
#    iterating_array = a.clone
#    a.each do |m|
#        num = m
#        iterating_array.each do |m|
#            solutions[num] = 1
#            num |= m
#        end
#        solutions[num] = 1
#        iterating_array.shift
#    end
#    solutions.keys.length
#end


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = set()
        for a in A:
            cur = {p | a for p in cur} | {a}
            ans |= cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        my_set = [set([A[i]]) for i in range(len(A))]
        
        for i in range(1, len(A)):
            for prev_result in my_set[i-1]:
                my_set[i].add(A[i] | prev_result)
                
        return len(set.union(*my_set))
                
            


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        
        curr=set()
        ans=set()
        for a in A:
            s=set()
            s.add(a)
            for i in curr:
                s.add(a|i)
            curr=s
            for t in curr:
                ans.add(t|a)
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        my_set = [set([A[i]]) for i in range(len(A))]
        
        for i in range(1, len(A)):
            for prev_result in my_set[i-1]:
                res = A[i] | prev_result
                my_set[i].add(res)
                
        return len(set.union(*my_set))
                
            


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        sets=[{i} for i in A]
        for i in range(1,len(A)):
            for prev in sets[i-1]:
                sets[i].add(A[i]|prev)
        
        for num in sets[1:]:
            sets[0]|=num  
        return len(sets[0])

from typing import List, Set


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        all_results: Set[int] = set()
        prev_results: Set[int] = set()

        for start_index in range(len(A)):
            curr_results: Set[int] = set()
            curr_results.add(A[start_index])

            for prev_result in prev_results:
                curr_results.add(prev_result | A[start_index])

            all_results |= curr_results
            prev_results = curr_results
        return len(all_results)



class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res, curr = set(), set()
        for a in A:
            temp = {a}
            for b in curr:
                temp.add(a | b)
            curr = temp
            for num in curr:
                res.add(num)
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        sets=[{i} for i in A]
        for i in range(1,len(A)):
            for prev in sets[i-1]:
                sets[i].add(A[i]|prev)
        return len(set.union(*sets))

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        prev = set()
        prev.add(0)
        
        for i in range(len(A)):
            cur = set()
            cur.add(A[i])
            
            for p in prev:
                res = p | A[i]
                if res != p:
                    ans.add(p)
                cur.add(res)
            
            prev = cur
        
        for p in prev:
            ans.add(p)
        
        if 0 not in A:
            ans.remove(0)
        
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = set()
        for x in A:
            cur = {y|x for y in cur} | set([x])
            ans |= cur
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        my_set = set(A)
        curr = 0
        prev = set()
        prev.add(A[0])
        for num in A[1:]:
            temp = set()
            for p in prev:
                temp.add(num | p)
                my_set.add(num | p)
            prev = temp
            prev.add(num)

        return len(my_set)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        if A == []:
            return 0
        # count = [0]
        # dic = {}
        # def OR(s):
        #     if len(s) == 1:
        #         return s[0]
        #     res = s[0]
        #     for item in s[1:]:
        #         res = res | item
        #     return res
        # for i in range(len(A)):
        #     for j in range(i, len(A)):
        #         res = OR(A[i:j+1])
        #         if res in dic:
        #             continue
        #         dic[res] = 0
        #         count[0] += 1
        # return count[0]
        my_set = set(A)
        curr = 0
        prev = set()
        prev.add(A[0])
        for num in A[1:]:
            temp = set()
            for p in prev:
                temp.add(num | p)
                my_set.add(num | p)
            prev = temp
            prev.add(num)

        return len(my_set)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set(A)
        prev = set([A[0]])
        for i in A[1:]:
            temp = set()
            for p in prev:
                temp.add(i|p)
                ans.add(i|p)
            prev = temp
            prev.add(i)
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # res, cur = set(), set()
        # for num in A:
        #     cur = {val | num for val in cur} | {num}
        #     res |= cur
        # return len(res)
        
        # list
        res = []
        left, right = 0, 0
        for val in A:
            right = len(res)
            res.append(val)
            for i in range(left, right):
                if res[-1] != (res[i] | val):
                    res.append(res[i] | val)
            left = right
        return len(set(res))


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res = set()
        
        last = set()
        
        for x in A:
            new = {x}
            
            for y in last:
                new.add(x | y)
            
            res |= new
            last = new
            
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        vals = set()
    
        if len(A) < 2:
            return len(A)
        
        cur = {0}
        for a in A:
            cur = {a| y for y in cur} | {a}
            vals |= cur
        return len(vals)

class Solution:
    def subarrayBitwiseORs(self, A):
        # Tabulation is a list of sets, one for each number in A. 
        # Each set, at position i, is initialised to containing the element at A[i]
        tabulation = [set([A[i]]) for i in range(len(A))]
        
        # And now we need to go through, updating the sets based on the previous set.
        for i in range(1, len(A)):
            for previous_result in tabulation[i - 1]: 
                tabulation[i].add(A[i] | previous_result)  
        
        # Return the number of unique numbers in the tabulation list.
        return len(set.union(*tabulation)) if len(A) > 0 else 0


class Solution:
    def subarrayBitwiseORs(self, A: list) -> int:
        results = set()
        pre = {0}

        for a in A:
            '''
            cur = {a}
            for prev in pre:
                cur.add(prev | a)
            results |= cur
            pre = cur
            '''
            pre = {a | p for p in pre} | {a}
            results |= pre

        return len(results)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        s, ans = set(), set()
        for a in A:
            s = {a} | {a | b for b in s}
            ans |= s
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # https://blog.csdn.net/fuxuemingzhu/article/details/83511833
        res = set()
        cur = set()
        for a in A:
            cur = {n | a for n in cur} | {a}
            res |= cur
        return len(res)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        s = set()
        s1 = set()
        for n in A:
            s2 = set()
            for e in s1:
                s2.add(e|n)
            s1=s2
            s1.add(n)
            s|=s1
        # print(s)
        return len(s)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res = set([])
        tmp = set([])
        for i in A:
            newtmp = set([])
            for j in tmp:
                newtmp.add(i|j)
                res.add(i|j)
            newtmp.add(i)
            res.add(i)
            tmp = newtmp
        return len(res)
            
                
            


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # 12:57 8/24/20
        
        res, cur = set(), set()
        for i in A:
            cur = {i | j for j in cur} | {i}
            res |= cur
        return len(res)
            
                


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans, frontier = set(), set()
        
        for n in A:
            frontier = {x | n for x in frontier if x|n != -1}
            frontier.add(n)
            ans |= frontier
        
        
        return len(ans)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        curr = {0}
        ans = set()
        for a in A:
            curr = {x|a for x in curr } | {a}
            ans |= curr
        return len(ans)
    


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        my_set = [set([A[i]]) for i in range(len(A))]
        ans = set(A)
        
        for i in range(1, len(A)):
            for prev_result in my_set[i-1]:
                res = A[i] | prev_result
                my_set[i].add(res)
                ans.add(res)
                
        return len(ans)
                
            


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        my_set = set(A)
        curr = 0
        prev = set()
        prev.add(A[0])
        for num in A[1:]:
            temp = set()
            curr |= num
            my_set.add(curr)
            prev.add(num)
            for p in prev:
                temp.add(num | p)
                my_set.add(num | p)
            prev = temp

        return len(my_set)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        dp = []
        for i in range(len(A)):
            if i == 0:
                dp.append(set([A[i]]))
            else:
                inner = set([A[i]])
                for d in dp[-1]:
                    inner.add(d | A[i])
                dp.append(inner)
        total = set()
        for d in dp:
            total.update(d)
        return len(total)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        result = set()
        curr = set()
        for num in A:
            curr = {num | prev_num for prev_num in curr} | {num}
            result |= curr
        return len(result)
        
        
        
#         result = set()
#         prev = set([0])
#         for num in A:
#             curr = set([num])
#             for prev_num in prev:
#                 curr.add(prev_num | num)
#             result |= curr
#             prev = curr
#         return len(result)


class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        ans = set()
        current = {0}
        for x in arr:
            # print(x,current)
            current = {x | y for y in current} | {x}
            # print(current)
            ans |= current
            # print(ans)
        return len(ans)
    
        # brute force time complexity :O(n^2)
        # space complexity:O(n)
        if not arr:return 0
        l ,ans = len(arr) ,set()
        for i in range(l):
            res = arr[i]
            ans.add(res)
            for j in range(i+1,l):
                res |= arr[j]
                ans.add(res)
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, a: List[int]) -> int:
        res, prev = set(), set()
        res.add(a[0])
        prev.add(a[0])
        for i in range(1, len(a)):
            cur = set()
            cur.add(a[i])
            res.add(a[i])
            for j in prev:
                cur.add(j|a[i])
                res.add(j|a[i])
            prev = cur
        return len(res)

class Solution(object):
    def subarrayBitwiseORs(self, A):
        final = set()
        actual = set()
        for el in A:
            actual = {el} | {el2 | el for el2 in actual}
            final |= actual
        return len(final)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        mp={0:1} 
        ans={} 
        for a in A:
            temp={} 
            for m in mp:
                temp[m|a]=1 
            temp[a]=1 
            for t in temp:
                ans[t]=1 
            mp={} 
            for t in temp:
                mp[t]=1 
        cnt=0 
        for c in ans:
            cnt+=1 
        return cnt
            


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        result_set = set()
        results = set()
        for num in A:
            results = {j | num for j in results}
            results.add(num)
            result_set.update(results)
        return len(result_set)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        
        ans = set()
        prev = set()
        
        for a in A:
            
            cur = set(a | b for b in prev)
            cur.add(a)
            
            prev = cur
            ans |= cur
            
        return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # O(N^3) to try oring every possible subarray
        
        # key fact: for any number k , k | k = k
        # also 0 | k = k for all k
        
        # one small optimization: scan through and delete any 0s or consecutive repeats
        
        # keep a list of or results s.t. or[i] = set of all possible results from oring subarrays that end at i
        # then or[i] = [A[i]] + [A[i] | res for res in or[i - 1]] -> use a set to prune dups at each step
        #    you can just keep or[i] for most recent two i's
        # 
        if not A:
            return []
        # [1, 2, 4]
        # all_outcomes: {1, 2, 3, 4, 6, 7}
        # outcomes: {2, 3}
        # 4: temp {4, 6, 7}
        
        # todo(mywang): preprocess array and remove unnecessary stuff
        # for i in range(len(A))[::-1]:
        #     if (i > 0 and A[i] == A[i - 1]):
        #         A.pop(i)
        all_outcomes = set()
        outcomes = set()
        for elt in A:
            outcomes = {elt} | {elt | val for val in outcomes}
            all_outcomes |= outcomes
        
        return len(all_outcomes)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # O(N^3) to try oring every possible subarray
        
        # key fact: for any number k , k | k = k
        # also 0 | k = k for all k
        
        # one small optimization: scan through and delete any 0s or consecutive repeats
        
        # keep a list of or results s.t. or[i] = set of all possible results from oring subarrays that end at i
        # then or[i] = [A[i]] + [A[i] | res for res in or[i - 1]] -> use a set to prune dups at each step
        #    you can just keep or[i] for most recent two i's
        # 
        if not A:
            return []
        # [1, 2, 4]
        # all_outcomes: {1, 2, 3, 4, 6, 7}
        # outcomes: {2, 3}
        # 4: temp {4, 6, 7}
        
        # todo(mywang): preprocess array and remove unnecessary stuff
        for i in range(len(A))[::-1]:
            if (i > 0 and A[i] == A[i - 1]):
                A.pop(i)
        all_outcomes = set()
        outcomes = set()
        for elt in A:
            outcomes = {elt} | {elt | val for val in outcomes}
            all_outcomes |= outcomes
        
        return len(all_outcomes)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # O(N^3) to try oring every possible subarray
        
        # key fact: for any number k , k | k = k
        # also 0 | k = k for all k
        
        # one small optimization: scan through and delete any 0s or consecutive repeats
        
        # keep a list of or results s.t. or[i] = set of all possible results from oring subarrays that end at i
        # then or[i] = [A[i]] + [A[i] | res for res in or[i - 1]] -> use a set to prune dups at each step
        #    you can just keep or[i] for most recent two i's
        # 
        if not A:
            return []
        # [1, 2, 4]
        # all_outcomes: {1, 2, 3, 4, 6, 7}
        # outcomes: {2, 3}
        # 4: temp {4, 6, 7}
        
        # todo(mywang): preprocess array and remove unnecessary stuff
        for i in range(len(A))[::-1]:
            if (i > 0 and A[i] == A[i - 1]):
                A.pop(i)
        all_outcomes = set([A[0]])
        outcomes = set([A[0]])
        for elt in A[1:]:
            temp = {elt} | {elt | val for val in outcomes}
            outcomes = temp
            all_outcomes |= outcomes
        
        return len(all_outcomes)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        cur,res = set(),set()
        for i in A:
            cur = { i|j for j in cur} | {i}
            res |= cur
        return len(res)
#        nums, n = set(), len(A)
#        for i in range(n):
#            num = A[i]
#            for j in range(i, n):
#                num |= A[j]
#                nums.add(num)
#        return len(nums)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        
        
        
        # my solution ... 736 ms ... 100 % ... 40.6 MB ... 15 %
        #  time: O(nlogn)
        # space: O(logn)
        
        res = set()
        tot = set()
        for a in A:
            res = {prev | a for prev in res} | {a}  # 得出以当前 a 结尾的 subarray
            tot |= res                              # 把结果并入 tot
        return len(tot)
        
        


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        res = set()
        
        cur = set()
        
        for x in A:
            cur = {x} | {x | y for y in cur}
            res |= cur
            
        return len(res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
       # Frontier Set    
       # Time  complexity: O(NlogW), where N is the length of A, and W is the maximum size of elements in A.
       # Space complexity: O(NlogW)
       ans = set()
       cur = {0}
       for x in A:
           cur = {x | y for y in cur} | {x}
           ans |= cur
       return len(ans)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        # 12:57 8/24/20
        
        cur, res = set(),set()
        for num in A:
            cur = {num | j for j in cur} # | {num}
            # cur = set(num | k for k in A)
            cur.add(num)
            res.update(cur)
        
        return len(res)
        
        
                
        # res, cur = set(), set()
        # for i in A:
        #     cur = {i | j for j in cur} | {i}
        #     res |= cur
        # return len(res)

            
                


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        self.res = set()
        def helper(idx):
            if idx < 0:
                return set()
            if idx==0:
                self.res |= {A[idx]}
                return {A[idx]}
            val = {A[idx]}|{x|A[idx] for x in helper(idx-1)}
            self.res |= val
            return val
        helper(len(A)-1)
        return len(self.res)

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        result = set()
        curr = set()
        for num in A:
            curr = {num | prev_num for prev_num in curr}
            curr.add(num)
            result.update(curr)
        return len(result)
        
        
        
#         result = set()
#         prev = set([0])
#         for num in A:
#             curr = set([num])
#             for prev_num in prev:
#                 curr.add(prev_num | num)
#             result |= curr
#             prev = curr
#         return len(result)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        my_set = set(A)
        curr = 0
        prev = set()
        prev.add(A[0])
        for num in A[1:]:
            temp = set()
            #curr |= num
            #my_set.add(curr)
            
            for p in prev:
                temp.add(num | p)
                my_set.add(num | p)
                
            #print(temp)
            prev = temp
            prev.add(num)

        return len(my_set)


class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
       # Frontier Set    
       # Time  complexity: O(NlogW) = O(30N), where N is the length of A, and W is the maximum size of elements in A.
       # Space complexity: O(NlogW)
       ans = set()
       cur = {0}
       for x in A:
           cur = {x | y for y in cur} | {x}
           ans |= cur
       return len(ans)


class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        s = set()
        prev = set()
        prev.add(arr[0])
        s.add(arr[0])
                        
        for i in range(len(arr)):
            temp = set()
            for val in prev:
                temp.add(val|arr[i])
                s.add(val|arr[i])
                
            prev = temp
            prev.add(arr[i])
            s.add(arr[i])
        
        return len(s)