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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Bit manipulation

Data structures

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:
		if not A:
			return []
		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)


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:
			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:
		res = set()
		tot = set()
		for a in A:
			res = {prev | a for prev in res} | {a}
			tot |= res
		return len(tot)


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:
		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 num in A:
			cur = {num | j for j in cur} | {num}
			res.update(cur)
		return len(res)


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:
		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)
		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)


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:
		(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)


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:
		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:
		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 = []
		(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 = [set([A[i]]) for i in range(len(A))]
		for i in range(1, len(A)):
			for previous_result in tabulation[i - 1]:
				tabulation[i].add(A[i] | previous_result)
		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:
			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:
		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
		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:
		(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:
		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)


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:
		if not A:
			return []
		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:
		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:
		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, 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)