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
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?