Fast algorithm for checking if binary arrays can be rotated to not have an elementwise sum over 1 : <p>Let's say I have a set of constant-length arrays containing only zeroes and ones. My goal is to find out whether, after any rotation of any of the arrays, the element-wise sums of the arrays will not exceed 1.</p>

<p>For instance, let's say I have the following three arrays: <code>[1, 0, 0, 0], [1, 0, 1, 0]</code>, and <code>[1, 0, 0, 0]</code>. I can rotate the second array by one element and the third array by two elements to obtain the arrays <code>[1, 0, 0, 0], [0, 1, 0, 1], [0, 0, 1, 0]</code>, the element-wise sum of which is <code>[1, 1, 1, 1]</code>. However, had I not applied the rotations, I would have gotten a sum of <code>[3, 0, 1, 0]</code>, which does not fit my requirements as one of the elements (the 3) is greater than 1.</p>

<p>Now, my question is, what is a fast way to determine if this is possible for an arbitrary number of arrays? For instance, there is no way to rotate <code>[1, 0, 0, 0], [1, 0, 1, 0], [1, 0, 1, 0]</code> so that the elements of the sum do not exceed 1.</p>

<p><strong>Current heuristics</strong></p>

<p>Obviously, if the total sum of the arrays, which are, say,  length <code>n</code>, exceeds <code>n</code>, then this is trivially impossible.<br>
The best idea for an approach I can think of so far is taking two arrays, finding a way to merge them together, and inverting the result. Then, we take this result and the next array, and repeat this process. However, this method does not guarantee to find a solution if one exists.</p>

<p>My question is, short of trying every possible rotation, what would be a good algorithm for this problem?</p>
