h2(#multimi2). 'Multimi 2':problema/multimi2

Daca $N$ este de forma $4*p$ vom imparti cele $N$ numere in grupe de cate patru numere de forma $4k, 4k+1, 4k+2, 4k+3$. Observam ca $4k-(4k+1)-(4k+2)+(4k+3)=0$. Numerele de forma $4k$ si $4k+3$ le vom plasa in prima multime iar celelalte in a doua multime si vom obtine diferenta $0$ minim posibila. Daca $N$ da restul $1$ la impartirea cu $4$, $N-1$ este divizibil cu $4$, vom imparti numerele de la $2$ la $N$ in grupe de cate patru ca la pasul anterior si vom plasa numarul $1$ in oricare din cele doua multimi si vom obtine diferenta $1$. Daca $N$ da restul $2$ la impartirea cu $4$, vom incepe prin a imparti numerele de la $3$ la $N$ iar apoi pe $1$ il vom introduce intr-o multime iar pe $2$ in cealalta, astfel vom obtine diferenta $1$. Daca $N$ da restul $3$ la impartirea cu $4$ vom imparti in grupe de cate patru numerele de la $4$ la $N$, numerele $1$ si $2$ le vom introduce intr-o multime, iar $3$ in cealalta si vom obtine diferenta $0$.

Daca $N$ este de forma $4*p$ vom imparti cele $N$ numere in grupe de cate patru numere de forma $4k, 4k+1, 4k+2, 4k+3$. Observam ca $4k-(4k+1)-(4k+2)+(4k+3)=0$. Numerele de forma $4k$ si $4k+3$ le vom plasa in prima multime iar celelalte in a doua multime si vom obtine diferenta $0$ minim posibila. Daca $N$ da restul $1$ la impartirea cu $4$, $N-1$ este divizibil cu $4$, vom imparti numerele de la $2$ la $N$ in grupe de cate patru ca la pasul anterior si vom plasa numarul $1$ in oricare din cele doua multimi si vom obtine diferenta $1$. Daca $N$ da restul $2$ la impartirea cu $4$, vom incepe prin a imparti numerele de la $3$ la $N$ iar apoi pe $1$ il vom introduce intr-o multime iar pe $2$ in cealalta, astfel vom obtine diferenta $1$. Daca $N$ da restul $3$ la impartirea cu $4$ vom imparti in grupe de cate patru numerele de la $4$ la $N$, numerele $1$ si $2$ le vom introduce intr-o multime, iar $3$ in cealalta si vom obtine diferenta $0$. Complexitatea solutiei este {$O(N)$}.