# Explanation of Editorial

https://codeforces.com/problemset/problem/243/A

It would be a great help if someone could explain the editorial of this question. I have been trying to understand it for a long time but simply couldn’t.

Consider all values f(l, r) with fixed r.

Claim: the number of such values is at most 20.
Because 0 \le a_i \le 10^6, which is slightly less than 2^{20}, the largest value of f(l,r) can have at most 20 bits. Now f(l-1, r) = a_{l-1}\ | \ f(l,r), which means the number of 1 bits in f(l-1,r) is \ge the number of 1 bits in f(l,r). However you can only increase the number of 1 bits until you hit 20, hence the claim is proved.

Let’s say you maintain a set of values f(l, r) for some r. This is quite doable because of the 20 value limit. Let’s call this set g(r). Then, g(r) = \{a_r\} \cup \{a_r \ | \ x : x \in g(r-1) \}, which basically means that you OR a_r with each value of g(r-1) to get the values of g(r) and also consider the value a_r itself. I suppose this can be considered dynamic programming.

If you calculate g(i) for all indices, the set of all possible values f(l,r) is \bigcup_{i=1}^n g(i). You just need to output the size of this set.

thanks a lot @meooow for such a good explanation.

Although, I have used a different approach ( prefix sum and binary search) and it gave me ACCEPTED

Could you share your approach? I’m interested to know.

//
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}