A jeweler is stringing a bracelet from n beads, and the i-th bead currently weighs nums[i] grams. For the clasp mechanism to balance correctly, every bead on the string must end up with the same parity of weight (all beads even, or all beads odd -- never a mix). The jeweler can top up any single bead's weight by exactly 1 gram, choosing beads and repeating as many times as needed; she never files weight down. Determine the minimum total number of 1-gram top-ups needed to reach a uniform parity across all beads, along with the resulting array of weights after applying an optimal set of top-ups. If both the "make everything even" and "make everything odd" targets can be reached with the same number of top-ups, output the weights for the "make everything even" target.
Line 1: a single integer n, the number of beads.
Line 2: n space-separated integers nums[0], ..., nums[n-1], the current bead weights.
Line 1: a single integer, the minimum number of top-ups.
Line 2: the n resulting bead weights, space-separated, in their original order.
Example 1
Input
4 1 2 3 4
Expected
2 2 2 4 4
Explanation
Two beads (1, 3) are odd and two beads (2, 4) are even. Making everything even costs 2 top-ups (1 -> 2 and 3 -> 4); making everything odd also costs 2 top-ups (2 -> 3 and 4 -> 5). The costs tie, so the even target is chosen: 2 top-ups, resulting weights [2, 2, 4, 4].
Example 2
Input
3 2 4 6
Expected
0 2 4 6
Explanation
All three beads are already even, so 0 top-ups are needed and the weights are unchanged: [2, 4, 6].
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →