Prima observaţie importantă este că <tex> !(a\ \oplus\ expresie)\ = \ !a\ \oplus\ expresie\ = \ a\ \oplus\ !expresie </tex> si ca <tex>!a\ \oplus\ !b\ =\ a\ \oplus\ b</tex>. Aşadar ne dăm seama că orice expresie poate fi rescrisă fără semne de negaţie sau cu un singur semn de negaţie, în funcţie de paritatea numărului semnelor de negaţie care apar în expresia iniţială.

Cum operaţia xor e asociativă şi comutativă şi <tex>a\ \oplus\ a =\ 0\ </tex>, putem scrie orice expresie fara paranteze si fiecare variabila sa apara fie o data, fie deloc. Astfel singurele expresii pe care trebuie sa le luam in considerare sunt cele cu maxim <tex> n </tex> variabile in care putem avea maxim un semn de negatie. In total sunt <tex>2^{(n+1)}</tex> astfel de expresii deci daca le-am genera pe toate si le-am evalua cu un backtracking, complexitatea finala ar fi <tex>O(2^{(2*n+1)})</tex>, o solutie care daca este suficient de bine optimizata poate sa ia $60$ de puncte.

Cum operaţia xor e asociativă şi comutativă şi <tex>a\ \oplus\ a =\ 0\ </tex>, putem scrie orice expresie fara paranteze si fiecare variabila sa apara fie o data, fie deloc. Astfel singurele expresii pe care trebuie sa le luam in considerare sunt cele cu maxim n variabile in care putem avea maxim un semn de negatie. In total sunt <tex>2^{(n+1)}</tex> astfel de expresii deci daca le-am genera pe toate si le-am evalua cu un backtracking, complexitatea finala ar fi <tex>O(2^{(2*n+1)})</tex>, o solutie care daca este suficient de bine optimizata poate sa ia $60$ de puncte.

Ne dam seama ca daca pe prima pozitie din sirul de biti apare $1$, atunci semnul de negatie apare neaparat. La fel daca pe prima pozitie din sirul de biti apare $0$, atunci nu avem semn de negatie. Astfel putem determina in <tex>O(1)</tex> daca avem negatie sau nu. Daca avem negatie, putem nega intreg sirul de biti si putem rezolva problema la fel ca in cazul in care nu avem negatie.