Codeforces 1360C. Similar Pairs Solution

Let e — be the number of even numbers in the array, and o — be the number of odd numbers in the array. Note that if the parities of e and of o do not equal, then the answer does not exist. Otherwise, we consider two cases:

e and o — are even numbers. Then all numbers can be combined into pairs of equal parity.

e and o — are odd numbers. Then you need to check whether there are two numbers in the array such that the modulus of their difference is 1. If there are two such numbers, then combine them into one pair. e and o will decrease by 1 and become even, then the solution exists as shown in the previous case.

Solution in C++:

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh  

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5. int n,i,f,e,o,t,d;
6. cin>>t;
7. while(t--)
8. {
9. e=0,o=0,f=0;
10. cin>>n;
11. int a[n+9];
12. for(i=0; i<n; i++)
13. {
14. cin>>a[i];
15. if(a[i]%2==1)
16. o++;
17. else
18. e++;
19. }
20. sort(a,a+n);
21. for(i=1;i<n;i++)
22. {
23. d=a[i]-a[i-1];
24. if(d==1)
25. {
26. f=1;
27. break;
28. }
29. }
30. if(e%2!=o%2)
31. cout<<"NO"<<endl;
32. else if(e%2==0&&o%2==0)
33. cout<<"YES"<<endl;
34. else if (e%2==1&&o%2==1&&f==1)
35. cout<<"YES"<<endl;
36. else
37. cout<<"NO"<<endl;
38. }
39. }