Michael's Notes & Blog

The problem: We have an array 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 ary only counted once in the final answer.)

possible approaches: of course the first thing come to my mind is the brute force approch, but I know that it barely the right way to go in such kind of problems, since if solve every problem the brute force way, then way borther learning algorithms.

The next thing to try is some kind of prefix array to store the temporary results, for example we can have a array, in which the element prefix[i] is the OR of all the elements from the begining of the input array up to A[i], and then we can use prefix[i] and prefix[j] to compute the results for A[i] ... A[j]. However this approach is not working in this problem.

Another approach(and the right approach for this problem) Another approach is that we use a container to store the temporary results, and when we see a new element n, we use |= to update each element in the container, and we also add the new element n to the container, this is actually very like the prefix approch, in which we keep track of the results from the begining to a certain element, but in this case, we keep track of the results from each of the elements before a certain element to that element.