Brainstorm

 

This is Counting Problem!!!

This was one of those problems that just tests your patience to the limits and obliges you to fully exhaust your mind, and not to mention I had a math exam today, and yesterday 6 hours of sleep. Yes, I started thinking about this one from like 1 hour ago, that is 10:35p.m. something, and it's 11:35 right now. You can read the problem statement and try it on your own, but I would just say that negative and negative are not always positive...well, it wasn't the first time I had attempted this problem, this one is an old enemy, last time, I couldn't figure this out and from then it was in my tabs, now I am taking the problems for which I wasn't able to come up with an idea. 

The good part was that after the torture of 1 hour thinking about all the corner cases and all the possibilities that were possible, my code passed all the test cases in the first go. And I think that this is an important point that, many times we just come up with an idea not thinking about it much and we just run it hoping that it will pass, but the thing is that the more you think about the problem the better it is for you although it is very difficult to think about these tricky problems with full concentration but that's what is required, it took me 1 hour to understand the core of this problem, but someone with more focus, concentration, or experience could have done it in less time, also I was feeling difficulty with focusing because I generally can't function if I get less than 8 hours of sleep.

I think now I am gonna hit the bed before my brain starts throwing fatal errors on me, it has already processed a lot.....well, the

Problem

You are given an array $�=[{�}_1,{�}_2,\dots ,{�}_{�}]$.

Is it possible to partition $�$ into two non-empty subsequences ${�}_1$ and ${�}_2$ such that $���({�}_1)\times ���({�}_2)$ is odd?

Here, $���({�}_1)$ denotes the sum of elements in ${�}_1$, and $���({�}_2)$ is defined similarly.

Note: ${�}_1$ and ${�}_2$ must partition $�$, that is:

• ${�}_1$ and ${�}_2$ must be non-empty
• Every element of $�$ must be in either ${�}_1$ or ${�}_2$
• ${�}_1$ and ${�}_2$ must be disjoint (in terms of which indices their subsequences represent)

Input Format

• The first line of input will contain a single integer $�$, denoting the number of test cases.
• Each test case consists of 2 lines of input.
  • The first line of each test case contains a single integer $�$, the size of the array.
  • The next line contains $�$ space-separated integers ${�}_1,{�}_2,\dots ,{�}_{�}$: the elements of the array.

Output Format

For each test case, print on a new line the answer: YES if the array can be partitioned into two subsequences satisfying the condition, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, YES, yes, YEs, and yEs will all be treated as equivalent.

Constraints

• $1\le �\le 10^5$
• $2\le �\le 10^5$
• $1\le {�}_{�}\le 10^9$
• The sum of $�$ across all test cases won't exceed $10^6$.

Sample 1:

Input

Output

4
4
1 1 2 2
6
1 2 4 6 8 10
2
3 5
3
1 3 5

YES
NO
YES
NO

Explanation:

Test case $1$: We have $�=[\underset{‾}{1},1,\underset{‾}{2},2]$. Let ${�}_1$ be the underlined elements and ${�}_2$ be the other ones. $���({�}_1)\times ���({�}_2)=3\times 3=9$.

Test case $2$: It can be proved that no partition of $�$ into ${�}_1,{�}_2$ satisfies the condition.

Test case $4$: Choose ${�}_1=\{3\},{�}_2=\{5\}$.

Test case $4$: It can be proved that no partition of $�$ into ${�}_1,{�}_2$ satisfies the condition.

This is the code for the above problem, try to think about the solution

of the problem on your own and after that try to understand this code

T=int(input())

while(T):

    n=int(input())

    nums=list(map(int,input().split()))

    odd_count,even_count=0,0

    for i in nums:

        if(i%2==0):

            even_count+=1

        else:

            odd_count+=1

    # When there are odd numbers with count less than equal to 1

    if(odd_count<=1):

        print("NO")

        T-=1

        continue

    # When there is no even number in the array

    if(even_count==0):

        if(odd_count%2!=0 or (odd_count/2)%2==0):

            print("NO")

        # elif((odd_count/2)%2!=0):

        #     print("YES")

        else:

            print("YES")

        T-=1

        continue

    # Now till here we know that we have odd_count greater than equal to 2 and also

    # we have 1 or more even numbers

    if(odd_count%2==0):

        print("YES")

    else:

        print("NO")

    T-=1