can someone provide easy editorial of Chang and Bitwise OR problem of july cook-off?

PS:im not getting the concept from setter editorial.

I’m not sure if this comment of mine will be enough for you.

Let’s say we have three numbers: 1 5 3. The possible subsequence of these 3 numbers are the ff:

(1 | 5 | 3) = 7

(1 | 5) | 3 = 7

1 | (5 | 3) = 7

As you can see, no matter what subsequence you used, you will still arrive in the same answer. Because subsequence OR of elements in an array has associative property (just like in addition)

1 Like

Hi @vivek96 . Maybe you would want to look at this comment for some math proof. Good luck.

Also the thing is you will get minimum answer by doing this only because if you try
1|5+3 = 8
1|3+5 = 8
Or you can try any example

1 Like

The concept is that, bitwise OR will be equivalent to ‘+’ in worst case, and in best case, number will be unchanged.

Eg- 5|5=5 (no change)

8|7=1000|0111=15 (eq to addition)

Its obvious that we will get minimum score if we take entire array as a segment and take “OR” or all elements in the array. Take some examples to get it, you will see that for two numbers A and B, A|B<=A+B

4 Likes

This may not be a good explanation.But i am trying my level best!

Let’s say for an element in the array ith bit is set,then the OR-sum of the sequence which contains this particular element should contain 2^i(pow(2,i)) in the sum.In the same manner for all the sequences if ith bit is set for atleast one number in that sequence then 2^i will be there in the OR-sum of that sequence.Adding 2^i more than one time won’t give you an optimal sum here.so we just want to take all the numbers having some particular bit in to the same sequence which is nothing but ORsum of all the numbers.

1 Like

not getting that proof.can u explain that proof?

thanks a lot @vijju123

//