0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ What is the source of this problem? It is very similar to math.stackexchange.com/questions/1595964/… . Is this part of programming competition? $\endgroup$ – lulu Jan 2 '16 at 13:06
  • $\begingroup$ Damn. I searched a lot for it. But couldn't find it. I'm having trouble using stack exchange. Can you help me ? $\endgroup$ – Aaron Stone Jan 2 '16 at 13:09
  • 1
    $\begingroup$ 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? $\endgroup$ – lulu Jan 2 '16 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.