3875. Construct Uniform Parity Array I

Difficulty: Easy | Published on 2026-09-03

This one is a nice change of pace — it's "Easy," and the real challenge isn't writing complicated code, it's spotting a clean mathematical proof hiding inside the problem. Let's build it up from zero.

1. Problem in Very Simple Language

You have an array INLINECODE0 of numbers, all different from each other.

You must build a second array INLINECODE1, same length, where every single element of INLINECODE2 is even, OR every single element is odd — you pick which one, but you can't mix.

For each position INLINECODE3 in INLINECODE4, you're allowed to fill it in with one of two choices:

Just copy the number straight over: INLINECODE5, or Subtract some other number in the array from it: INLINECODE6 (where INLINECODE7 is any other valid position, not INLINECODE8 itself).

You get to make this choice independently for every position — some positions can use the "copy" option while others use the "subtract" option, however you like.

What's given: the array INLINECODE9. What to find: is there some way to fill in INLINECODE10 (mixing copy/subtract choices freely) so that everything ends up the same parity (all even or all odd)? What to return: INLINECODE11 if possible, INLINECODE12 if not.

2. Real-Life Analogy

Imagine a row of lockers, each with a number tag on it. For each locker, you're allowed to either keep its tag exactly as-is, OR swap it for "this locker's number minus some other locker's number." Your goal: end up with every single locker showing either an odd tag or an even tag — no mixing allowed. You get to decide, locker by locker, which trick to use.

3. Important Programming Concepts I Need First

Array
Concept: A numbered list of values. Example: INLINECODE13 — position 0 holds INLINECODE14, position 1 holds INLINECODE15. Why we need it: Our whole input and output are arrays.

Even and Odd numbers, and "Parity"

Concept: A number is even if it divides evenly by 2 (no remainder), and odd if it doesn't. "Parity" is just the general word for "is it even or odd?" — two numbers "have the same parity" if they're both even or both odd. Example: INLINECODE16 and INLINECODE17 have the same parity (both even). INLINECODE18 and INLINECODE19 have different parity. Why we need it: The entire goal of this problem — "all odd or all even" — is a statement purely about parity.
Subtraction and Parity (a key mathematical fact)
Concept: When you subtract one whole number from another, there's a simple, reliable rule for the parity of the result: INLINECODE20 INLINECODE21 INLINECODE22 INLINECODE23

In other words: subtracting an even number never changes parity. Subtracting an odd number always flips parity (even ↔ odd). Example: INLINECODE24 (even − even = even, parity unchanged). INLINECODE25 (even − odd = odd, parity flipped). Why we need it: This single fact is the entire engine behind solving this problem — figuring out exactly when we can and can't change a number's parity using the "subtract" option.

Loop

Concept: Repeats an action for every item in a list. Example: "Go through every number in INLINECODE26 and count how many are odd." Why we need it: We need to scan the array once to count odd numbers.
If/else
Concept: Branching logic based on a condition. Why we need it: We'll reason through a couple of "what if" scenarios based on how many odd numbers exist.
Boolean
Concept: A value that's either INLINECODE27 or INLINECODE28. Why we need it: Our answer is literally a INLINECODE29/INLINECODE30 value.

4. Understand the Input

Take Example 1: CODEBLOCK0

Position 0 holds INLINECODE31 (even). Position 1 holds INLINECODE32 (odd). We're asked: can we build INLINECODE33, same length, where we independently choose "copy" or "subtract another element" at each position, such that the result is either fully odd or fully even? Why does it matter that INLINECODE34 is even and INLINECODE35 is odd? Because whether we can change a number's parity (via subtraction) depends entirely on whether there's an odd number elsewhere in the array to subtract (as we'll prove in a moment).

5. Understand the Output

Output: INLINECODE36

The example shows: INLINECODE37 (odd!), and INLINECODE38 (already odd). Both final values are odd, so the "all odd" target was achieved. Notice INLINECODE39 used the "subtract" trick to flip INLINECODE40 (even) into something odd, by subtracting the odd number INLINECODE41 — exactly matching our parity-flip rule from Section 3.

6. Solve the Example Manually

Let's manually reason through Example 1: INLINECODE42.

Step 1: Look at each element's own parity

Index	Value	Parity
0	2	even
1	3	odd

Step 2: Try target = "all even"

Index 1 (value INLINECODE43, odd) needs to become even. To flip its parity, we must subtract an odd number from it (per our rule). Is there an odd number at some other index? The only odd number in the whole array is INLINECODE44 itself, at index 1 — there's no other odd number anywhere else to use! So index 1 is stuck — it can't become even. Target "all even" fails.

Step 3: Try target = "all odd"

Index 0 (value INLINECODE45, even) needs to become odd. To flip its parity, we subtract an odd number from it. Is there an odd number at some other index? Yes — index 1 holds INLINECODE46, which is odd! So INLINECODE47, which is odd. ✔️ Index 1 (value INLINECODE48, odd) already matches the target — just copy it directly: INLINECODE49. ✔️ Target "all odd" succeeds!

Since at least one target (odd) works, the answer is INLINECODE50. ✔️ matches!

7. Think Like a Programmer

What do I know? For any element, I can either leave its parity alone (copy), or flip it (subtract an odd number, per our rule) — but flipping requires an odd number to exist somewhere else in the array. What do I need to find? Whether either "make everything even" or "make everything odd" is achievable. What can I try? Check both possible targets (all-even, all-odd) separately, and see if either one is achievable for every element. What happens if I try every possibility? There are only 2 targets to check (even or odd) — nowhere near an exponential search. This is naturally small and fast. Can I make it faster? It's already about as fast as it can be — but let's see if we can find an even deeper shortcut by understanding when each target succeeds or fails, using nothing more than counting. What information should I remember? Just one number: how many odd numbers are in the whole array (let's call it INLINECODE51). What pattern do I notice? For target "all even": every odd element needs to flip, which requires another odd element to subtract (not itself!). This is only impossible when there's exactly one odd number total (that lone odd number has no partner). For target "all odd": every even element needs to flip, which requires any odd element to exist somewhere in the array. This is only impossible when there are zero odd numbers total.

8. Start With the Brute Force Solution

Brute force idea: For each of the 2 possible targets (all-even, all-odd), check every element: if it already matches the target, fine; if not, check whether there's some other element with odd parity available to subtract (since only subtracting an odd number can flip parity). If every element can be satisfied, that target works — return INLINECODE52. If neither target works, return INLINECODE53.

Why it works: We're directly checking, for both possible goals, whether every element individually has a legal way to reach that goal — which is exactly the definition of "constructible."

Time complexity: For each of the 2 targets, we scan all INLINECODE54 elements, and for the ones that need to flip, we just need to know "does some odd number exist elsewhere?" — which we can precompute once (count of odd numbers) rather than re-scanning per element. So this is INLINECODE55 overall.

Space complexity: INLINECODE56 extra space (just a counter).

CODEBLOCK1

9. Explain the Brute Force Code Line by Line

INLINECODE57 — store the array length (used implicitly through INLINECODE58, though we don't strictly need INLINECODE59 elsewhere). The INLINECODE60 loop — walks through every element once, checking INLINECODE61 (true if the number is odd), incrementing INLINECODE62 each time we find one. This is the only pass we need over the actual array data. INLINECODE63 — not strictly required for the final answer, but useful to have named for clarity (everything that's not odd is even). INLINECODE64 — as reasoned in Section 7: target "all even" fails only when there's exactly one odd number (it has no other odd partner to flip with); it succeeds whenever there are zero odd numbers (nothing needs to flip at all) or two-or-more odd numbers (each odd element can always find some other odd element to pair with). INLINECODE65 — target "all odd" fails only when there are zero odd numbers anywhere (no odd number exists to use for flipping the evens); it succeeds as soon as at least one odd number exists anywhere in the array, since every even element can reuse that same odd number to flip. INLINECODE66 — the overall answer is INLINECODE67 if either target is achievable.

10. Why Is This Already "Ideal" — Nothing More to Optimize?

Unlike some earlier problems, there's no slow nested loop lurking here to eliminate — a single pass to count odd numbers, followed by two simple boolean checks, is already about as fast as any solution could be (INLINECODE68, which is required at minimum just to look at every input element once). So instead of "optimizing," let's dig one level deeper and discover something remarkable about this specific problem.

11. Find the Deeper Pattern

"Can we simplify this even further?"

Let's look very closely at our two conditions:

CODEBLOCK2

INLINECODE69 is INLINECODE70 only when INLINECODE71. INLINECODE72 is INLINECODE73 only when INLINECODE74.

These are two completely different, mutually exclusive numbers (INLINECODE75 can't simultaneously equal both INLINECODE76 and INLINECODE77)! That means it is mathematically impossible for both conditions to be false at the same time. At least one of them is always true, no matter what the array looks like.

⭐ Key Insight

Before the insight

It feels like we need to carefully check both targets and combine the results with INLINECODE78, expecting that sometimes both could fail, giving INLINECODE79.

The problem

It's not obvious at first that INLINECODE80 might never actually be reachable — the problem looks like it should sometimes be impossible, given it's phrased as a INLINECODE81/INLINECODE82 question.

The insight

The two failure conditions (INLINECODE83 for "all even," and INLINECODE84 for "all odd") can never both be true simultaneously, since INLINECODE85 is a single specific number and can't equal two different values at once. Therefore, for any valid input array, at least one of the two targets is always achievable — meaning the answer to this problem is always INLINECODE86, for every possible valid input!

After the insight

The entire problem reduces to a one-line proof rather than a computation: given the constraints (INLINECODE87, distinct positive integers), you can always construct a valid INLINECODE88. The "algorithm" becomes trivial — but understanding why is the actual point of the problem.

13. Dry Run — Confirming "Always True" on a Tricky Case

Let's test the trickiest possible scenario: exactly one odd number, to make sure the proof holds.

CODEBLOCK3

INLINECODE89 (only the value INLINECODE90 is odd). INLINECODE91 → INLINECODE92 → false. (Makes sense: the lone odd number INLINECODE93 has no other odd partner to flip to even.) INLINECODE94 → INLINECODE95 → true. Since INLINECODE96 is true, we go with target "all odd": Index 0 (INLINECODE97, odd): already matches, copy directly → INLINECODE98. Index 1 (INLINECODE99, even): flip using the odd number INLINECODE100 → INLINECODE101 (odd). ✔️ Index 2 (INLINECODE102, even): flip using the odd number INLINECODE103 → INLINECODE104 (odd). ✔️ Final INLINECODE105 — all odd! Construction succeeds, confirming INLINECODE106.

Even in this "worst case" for the even-target, the odd-target rescues us — exactly as the proof guarantees.

14. Optimized Code

CODEBLOCK4

CODEBLOCK5

15. Explain the Code Line by Line

Already covered in full detail in Section 9 — the logic is identical. The only "new" thing to internalize here is that, given the proof in Section 11, INLINECODE107 is a tautology (always true) for this specific problem's constraints — which is why the bare INLINECODE108 version is 100% equivalent and passes every test case.

16. Test With Multiple Examples

Example 1 — Normal Case

INLINECODE109 → INLINECODE110 → INLINECODE111, INLINECODE112 → Output: INLINECODE113 ✔️

Example 2 — Different Case

INLINECODE114 → INLINECODE115 → INLINECODE116 (nothing needs to flip), INLINECODE117 → Output: INLINECODE118 ✔️ (via the "all even" route, both already even, just copy directly)

Example 3 — Edge Case (single element)

INLINECODE119 → INLINECODE120, INLINECODE121 → INLINECODE122, INLINECODE123 (the single element INLINECODE124 is already odd, so target "all odd" is trivially satisfied by copying — no flip ever needed since there's nothing to flip) → Output: INLINECODE125 ✔️

17. Edge Cases

All elements already even (INLINECODE126) → target "all even" is trivially true (just copy everything); no flipping ever attempted. All elements already odd (INLINECODE127) → target "all odd" is trivially true (just copy everything). Exactly one odd element → target "all even" fails for that lone odd element (no partner), but target "all odd" always succeeds (that one odd number can flip every even element). Single-element array (INLINECODE128) → no other index ever exists to subtract from, so the only usable choice is "copy" — but that's always already uniform (trivially, one element is automatically "all the same parity" as itself). Large arrays with many mixed parities → still always works, since target "all odd" only ever needs one existing odd number as a universal helper for every even element.

18. Time Complexity

What is time complexity? A way to describe how much work an algorithm does as its input grows, using a general rule of thumb.

CODEBLOCK6

Why: We only need to look at each number once, to check whether it's odd. After that, the rest is just simple arithmetic on a single counted value — no nested loops, no repeated scanning. This is the fastest possible complexity for a problem that requires looking at every input element at least once (you can't know anything about numbers you haven't looked at).

19. Space Complexity

We only ever store a couple of counter variables (INLINECODE129, and optionally INLINECODE130) — none of which grow with the size of the input array.

So extra space used is INLINECODE131 — constant.

20. Common Mistakes Beginners Make

❌ "I need to actually try building INLINECODE132 element by element and check if it works, simulating the whole process." ✅ You never need to construct the actual array — you only need to reason about whether a valid construction exists, which boils down to counting odd numbers and checking two simple conditions.

❌ "Subtracting any other number flips the parity." ✅ Only subtracting an odd number flips parity. Subtracting an even number leaves parity unchanged — this distinction is the entire key to the problem.

❌ "If there's exactly one odd number, the answer must be tricky or possibly false." ✅ It initially seems that way (target "all even" indeed fails in that case), but target "all odd" always saves the day whenever there's at least one odd number — so this specific case still results in INLINECODE133.

❌ "I should check whether INLINECODE134 can equal INLINECODE135." ✅ The problem states INLINECODE136 for the subtraction option — but this restriction almost never actually matters here, since the "helper" element we use (an odd number, when flipping an even element, or vice versa) always has different parity from the element being flipped, so it can never be the same element anyway (a number can't simultaneously be both the element at index INLINECODE137 and have different parity from itself).

❌ "This problem needs a complex algorithm since it's asking about constructing an array." ✅ Not every construction problem requires simulating the actual construction — sometimes (as here), a short mathematical argument about feasibility is the entire solution, which is exactly why this is rated "Easy" despite sounding constructive.

21. How to Recognize This Pattern in Other Problems

Watch for these signal phrases:

CODEBLOCK7

Whenever a problem gives you a couple of simple per-element choices and asks "is it possible," try first asking: "under what condition would this be impossible?" — sometimes, as here, that condition turns out to be so narrow (or self-contradictory) that the answer is almost always (or literally always) achievable.

22. Interview Thinking

CODEBLOCK8

Applied here: the interview-winning move isn't clever code — it's spotting that the two "impossible" scenarios are mutually exclusive, so the answer collapses to a guaranteed INLINECODE138. Even if you don't fully prove this in the moment, the counting-based solution is a fully correct, efficient fallback.

23. Mini Challenge

Try these before checking the answers:

1. Why does subtracting an even number never change a value's parity, using the "even − even = even, odd − even = odd" facts from Section 3? 2. If INLINECODE139 has 5 elements, 4 of them odd and 1 even, which target (all-even or all-odd) is guaranteed to work, and why? 3. Can you construct any array (respecting the problem's constraints) where INLINECODE140 is simultaneously 0 and 1? Why or why not — and what does that tell you about this problem's answer?

Answer to Mini Challenge

1. Subtracting an even number keeps the "evenness contribution" unchanged: even − even stays even (removing an even amount doesn't cross an odd/even boundary), and odd − even stays odd (same idea) — in both cases, the original parity survives untouched. 2. Target "all odd" is guaranteed to work here: INLINECODE141, so the single even element can flip to odd using any of the 4 available odd numbers, and the 4 odd elements just copy directly. 3. No — INLINECODE142 is a single specific count of a fixed array; it's exactly one number, and can't be two different values at once. Since target "all even" only fails when INLINECODE143, and target "all odd" only fails when INLINECODE144, and these can never both hold true simultaneously, at least one target always succeeds — meaning this problem's answer is provably always INLINECODE145.

24. Final Revision

🧠 Problem in One Sentence
Determine whether INLINECODE146 can be transformed, index by index (copy or subtract-another-element), into an array that's entirely odd or entirely even.
🔑 Main Idea
Subtracting an even number never changes parity; subtracting an odd number always flips it — so target "all even" only fails when there's exactly one odd number, and target "all odd" only fails when there are zero odd numbers. These two failure conditions can never both hold, so one target is always achievable.
⚙️ Algorithm
1. Count how many elements in INLINECODE147 are odd (INLINECODE148). 2. Target "all even" is achievable unless INLINECODE149. 3. Target "all odd" is achievable unless INLINECODE150. 4. Return true if either target is achievable (which is provably always the case).
⏱️ Complexity
Time: INLINECODE151 Space: INLINECODE152
🎯 Pattern to Remember
When a problem offers per-element "keep or transform" choices tied to a simple property (like parity), check whether the two possible failure conditions can ever coexist — if they can't, the answer may be a guaranteed constant.

25. Beginner Quiz

1. (Understanding) Why does the problem allow INLINECODE153 to be any* other index, rather than requiring a specific relationship between INLINECODE154 and INLINECODE155? 2. (Basic concept) What is the parity of INLINECODE156? Of INLINECODE157? Explain using the "subtracting odd flips, subtracting even doesn't" rule. 3. (Logic) Why does target "all even" specifically fail when INLINECODE158, but succeed when INLINECODE159 or more? 4. (Dry run) For INLINECODE160, count the odd numbers, determine which target(s) work, and describe one valid construction of INLINECODE161. 5. (Complexity/pattern) Why can this problem be solved in INLINECODE162 time (or arguably INLINECODE163), and what does it mean for a "return true/false" problem to have a provably constant answer — how might you recognize this kind of situation in a different problem?