OppositeParity
SRM 778 · 2020-02-13 · by misof
Problem Statement
You are given a
- The elements of the new array have to remain the same, only their order may change.
- For each valid index i, the parity of the element at index i must change.
If there are multiple valid solutions, you may return any one of them.
If there are no valid solution, return an empty
Constraints
- A will have between 1 and 1,000 elements, inclusive.
- Each element of A will be between 0 and 999, inclusive.
{1, 4, 1, 4, 2, 1, 3, 5, 6, 2}
Returns: {6, 1, 2, 3, 1, 4, 2, 4, 5, 1 }
The original array and the new array written below each other: 1, 4, 1, 4, 2, 1, 3, 5, 6, 2 6, 1, 2, 3, 1, 4, 2, 4, 5, 1 We can easily verify that both properties are satisfied: all elements of the original array are in the new array, and the parity of the element at each index changed (e.g., at index 0 the odd number 1 was replaced by the even number 6).
{1, 1, 2}
Returns: { }
This array has no valid rearrangement. In particular, {2, 2, 1} is not a valid solution because it does not contain the same elements - it has more 2s and fewer 1s than the original array.
{3, 1, 4, 1, 5, 9}
Returns: { }
No solution here either.
{27, 18, 281, 828, 45, 90, 452, 3}
Returns: {452, 3, 90, 45, 828, 281, 27, 18 }
{7}
Returns: { }
Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class OppositeParity with a public method vector<int> rearrange(vector<int> A) · 116 test cases · 2 s / 256 MB per case