# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Kunj Rakesh Patel

*Nishank Suresh, Tejas Pandey*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1065

# PREREQUISITES:

None

# PROBLEM:

Given an array A of length N, it is possible to partition it into two non-empty subsequences such that the product of their sums is odd?

# EXPLANATION:

Suppose we were able to split A into two subsequences S_1 and S_2 satisfying the given condition.

Then, note that we want sum(S_1)\times sum(S_2) to be odd, which is only possible when sum(S_1) and sum(S_2) are both odd.

Further, S_1 and S_2 partition A, and so sum(S_1) + sum(S_2) = sum(A).

Since sum(S_1) and sum(S_2) must both be odd, sum(A) must be even.

So, if sum(A) is odd the answer is immediately â€śNoâ€ť.

From now on, letâ€™s consider sum(A) to be even.

If A contains only even numbers, then any subsequence also has even sum so splitting into two subsequences with odd sum is impossible.

On the other hand, if A contains an odd number, say x, then we can simply choose S_1 = \{x\} and S_2 to be all the other elements.

S_1 obviously has odd sum, and since sum(A) is even, S_2 also has odd sum and weâ€™re done.

So, the answer is â€śYesâ€ť if and only if sum(A) is even *and* A contains at least one odd number.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print('Yes' if sum(a)%2 == 0 and sum(x for x in a if x%2 == 1) else 'No')
```