Approach 1: Equal Ones
Each part has to have the same number of ones in their representation. The algorithm given below is the natural continuation of this idea.
S is the number of ones in
A. Since every part has the same number of ones, they all should have
T = S / 3 ones.
S isn't divisible by 3, the task is impossible.
We can find the position of the 1st, T-th, T+1-th, 2T-th, 2T+1-th, and 3T-th one. The positions of these ones form 3 intervals:
[i1, j1], [i2, j2], [i3, j3]. (If there are only 3 ones, then the intervals are each length 1.)
Between them, there may be some number of zeros. The zeros after
j3 must be included in each part: say there are
z of them
(z = S.length - j3).
So the first part,
[i1, j1], is now
[i1, j1+z]. Similarly, the second part,
[i2, j2], is now
If all this is actually possible, then the final answer is
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.