1
$\begingroup$

I came across this question on a programming contest although I was not able to solve it. The editorial was released later but it was super unhelpful, so I am asking it here.

You are given an array, in which you have to calculate sum of all possible subarrays' OR.

For example: $a = [1, 2, 3, 4, 5]$, then the answer would be $71$.

Click here to see how

How would I go about solving such a problem in less than quadratic time?

$\endgroup$

closed as off-topic by Namaste, Adrian Keister, Theoretical Economist, José Carlos Santos, user91500 Sep 16 '18 at 9:19

This question appears to be off-topic. The users who voted to close gave these specific reasons:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Theoretical Economist, José Carlos Santos, user91500
  • "This question is not about mathematics, within the scope defined in the help center." – Namaste, Adrian Keister
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You should define that a subarray is a contiguous set of elements of the array. Are you guaranteed that the elements are a run of numbers, or could the array be $[1,4,9,14,26]?$ Are you guaranteed that the elements are sorted? Please state the whole problem. $\endgroup$ – Ross Millikan Sep 15 '18 at 20:52
  • $\begingroup$ They are not a run of consecutive numbers and they are not sorted either. $\endgroup$ – Andrew Scott Sep 16 '18 at 7:23
0
$\begingroup$

One idea is to compute how much is contributed by each bit in the sum. If the array is length $n$ there are $\frac 12n(n+1)$ subarrays because you choose two positions with replacement, with the earlier being the start and the later being the end. For each bit position the OR of a subarray will be $1$ unless all the numbers in it have a $0$ in that location, so we want to count the runs of $0$s. A run of $k\ 0$'s will generate $\frac 12k(k+1)$ subarrays that have a zero in that bit. Add up the number of subarrays that have a $0$ in the position, subtract from the total number of subarrays, and you have the number of subarrays that have a $1$ in that position.

As an example I will use the array $[1,2,3,4,5,6,7,8,9,10]$. There are $\frac 12\cdot 10 \cdot 11=55$ subarrays. In the ones bit there are five runs of $0$'s, each of length $1$. Each of those contributes one subarray with a $0$ in the ones bit, so there are $50$ subarrays with a $1$ in the ones place, starting our sum with $50$. In the twos bit there is a run of $1$ from $1$, a run of $2$ from $4,5$, and a run of $2$ from $9,10$. These give $1+3+3=7$ subarrays that have a $0$ in the twos bit, so there are $48$ that have a $1$, contributing $96$ to the sum. In the fours bit there is a run of three $0$s to start off and a run of three at the end, so there are $12$ subarrays with a $0$ in the fours place, giving $43$ with a $1$ and contributing $172$ to the sum. Finally for the eights there is a run of $7$ numbers at the start with a $0$ which gives $28$ subarrays with a $0$ in the eights place, so $27$ with a $1$, contributing $216$ to the sum. The sum is then $50+96+172+216=534$

This approach is linear in the length of the array. The operations count also grows with the number of bits in the largest number. If you had a short array with large numbers it would be faster to compute each subarray, which is actually an $n^3$ process-there are about $\frac 12n^2$ subarrays of average length $\frac n2$. If you had a thousand numbers of billions of bits and you can do a bitwise OR as a single operation it would be more efficient to just compute each subarray.

$\endgroup$
  • $\begingroup$ I am not sure I understand. I asked for the bitwise OR of all subarrays but the answer discusses about XOR? $\endgroup$ – Andrew Scott Sep 16 '18 at 7:22
  • $\begingroup$ @AndrewScott: I meant OR everywhere. I don't know why I typed XOR. The argument is correct. I'll fix it. Thanks. It does not depend on the numbers being sorted or contiguous. $\endgroup$ – Ross Millikan Sep 16 '18 at 13:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.