Pari
Soluţia acestei probleme se foloseşte de noţiuni elementare din teoria grafurilor. Pentru început, considerăm un graf G format din mulţimea tuturor indicilor. Muchiile se vor construi între două noduri (i, j) astfel încât resturile împărţirii la doi a celor două numere să fie diferite iar cmmdc(i, j) ≥ d. În continuare, considerăm că nodurile au două culori: alb pentru indicii care au paritate corespunzătoare şi negru pentru indicii care nu au paritatea corespunzătoare. Rezultă că dacă nodurile negre vor dispărea atunci vom găsi o soluţie. Ideea ce se conturează este ca din fiecare nod negru să parcurgem graful în lăţime sau adâncime adunând alternativ +1 şi -1 pe muchii, adică la numerele de pe poziţiile indicate de capetele muchiei, până când găsim un alt nod negru. Observăm astfel că pe acest lanţ, singurele noduri care îşi vor schimba culoarea vor fi doar nodul sursă şi nodul destinaţie.
Complexitatea finală este O(n * m), unde n e numărul de elemente ale şirului S, iar m numărul de perechi ce se pot forma.
