# Algorithm : Select maximum number of Boxes to lift from N boxes

There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to lift the maximum number of boxes possible.

But there is a condition that must be fulfilled for the lifted boxes. For every pair of the lifted boxes, the $GCD$ of the weights of those should be greater than $1$.

Eg 1:
N=7
Weights - 13 2 8 6 3 1 9


We can lift the boxes $2, 3, 4, 5, 7$ in this order. These boxes have following weight- $2, 8, 6, 3,9$ respectively. Note that $gcd(2, 8), gcd(8, 6), gcd(6, 3),gcd(3, 9)$ $>1$.

Eg 2
N=6
Weight - 1 3 3 5 5 1


We can lift boxes numbered $2, 3$ as $gcd(3, 3) = 3 > 1$.

There is one more possible solution: We can lift boxes numbered $4, 5$ as $gcd(5, 5) = 3 > 1$.

I thought of a naive solution to check $GCD$ of every successive pair and eliminating that box with whom $GCD$ of next box will be equal to $1$. But this will be very time consuming and not efficient at all. It's time complexity will be quadratic or polynomial.

Now I can't figure out any better and efficient solution/algorithm to find the answer. Any help will be appreciated. Also I would like to keep the time complexity less than quadratic time like maybe $O(N*LOGN)$.

• You should mention that it is a problem from a recent programming contest. Competing with an answer received here would be cheating. – gnasher729 Dec 3 '16 at 17:15
• I'm voting to close this question as off-topic because it is part of a current contest. – David Richerby Dec 3 '16 at 19:29
• @DavidRicherby: Would it make sense to put the question on hold until the competition is over? And if that was done, would it be Ok to post an answer taken from the competition? – gnasher729 Dec 3 '16 at 22:32
• @gnasher729 Yes, I think it should be put on hold; I don't see any particular reason to keep it closed once the contest is over. We tend to prefer original answers to answers that are just quotations from some other source. It would probably be better to cite the competition answer in an answer that explained what was going on. – David Richerby Dec 3 '16 at 22:53

You could answer the question "what is the highest number of boxes that we can lift starting at box #k", for k = N, N-1, N-2, ..., 1 in that order.

For k = N the answer is obviously 1, and for every k the answer is obviously at least 1. To get the answer for one k, find the next box with gcd > 1; if none is found the answer is 1. If you found a box with gcd > 1 you examine further boxes that might improve the answer. Total time worst time is calculating n^2 / 2 GCD's.

In practice, you would set up some data structures to find out quickly whether a solution can be beaten. In your example, you would find that you can lift 4 boxes starting with box #3 but 3 or fewer starting with any later box, so when you see that gcd of box #2 and #3 is > 1, you know you can lift 5 boxes starting at #2, and you know this cannot be beaten.

• Sorry, I didn't get the hang of this. Correct me if I'm wrong, Isn't this similar to my approach i.e. by checking every box with successive box starting from last box? But is there any data structure that would reduce the time complexity ? – sammy Dec 3 '16 at 16:10
• There is always a data structure to reduce time complexity. And you asked for "better than polynomial" which would mean "high degree polynomial". Quadratic is better. And since you asked for the answer to a programming context, you should really do this yourself. I don't want to support cheating. – gnasher729 Dec 3 '16 at 17:16