# Minimum sum of the numbers added to elements of a set to meet the condition(mentioned below)?

Problem Statement :

We have to add different numbers(could be 0 too) to elements of a set so that gcd of all elements becomes greater than 1 and the set is arranged in ascending order.

Example : Set S = {5,4,7,6,8}

Now the best alteration to fit the above condition will lead to => {6,6,8,8,8}

So the answer will be 1+2+1+2+0 = 6

Till now I've done this :

1. Change the elements such that the set becomes sorted.

A0<=A1<=A2<=A3<=...<=An

2. Now if the set contains two or more distinct primes, increment all of them by 1.

3. Now, I thought seeing that if there are more even numbers than odd, then least sum would be equal to number of odd elements(each incremented by 1).

But I was wrong as : if S = {5,10,15,20,24} answer would be 1 (changing 24 to 25).

How should I tackle this problem ?

• What is the source of this problem? It is very similar to math.stackexchange.com/questions/1595964/… . Is this part of programming competition? – lulu Jan 2 '16 at 13:06
• Damn. I searched a lot for it. But couldn't find it. I'm having trouble using stack exchange. Can you help me ? – Aaron Stone Jan 2 '16 at 13:09
• I don't want to interfere with a live competition and when variants of an algorithm question start showing up at the same time, that's usually the source. Where does this problem come from? – lulu Jan 2 '16 at 13:12