0932EasyArrayMath

Nudging Pairs Towards One Parity

Tracked in this browser only

Trains the technique from

LeetCode 3875Construct Uniform Parity Array I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Counters are given as nums1, all of them different.

One nudge picks two different counters and adds one to each of them. Nudges may be repeated as often as you like, choosing any pair each time.

Return true when some sequence of nudges leaves every counter odd, or leaves every counter even.

Examples

Example 1

Input: nums1 = [14, 9, 27, 6]
Output: true

Two of the four counters are odd, and two is even, so nudging the two odd ones together leaves all four even.

Example 2

Input: nums1 = [1, 2]
Output: false

One counter is odd and one is even. A nudge flips both, so there is always exactly one odd counter and neither goal is reachable.

Example 3

Input: nums1 = [1, 2, 3]
Output: true

Two counters are odd and one is even. Nudging the odd pair leaves all three even.

Constraints

1 <= nums1.length <= 100
1 <= nums1[i] <= 100
The counters are all different

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def uniform_array(nums1: list[int]) -> bool:

Java

public boolean uniformArray(int[] nums1)

The intended approach

Time O(n) for n counters, one pass.Space O(1).

Only whether each counter is odd or even matters, since adding one always flips that and nothing else about the values is asked about. A nudge flips exactly two of them, so the number of odd counters changes by two, by nothing, or by minus two, and its parity therefore never changes at all. That is the whole invariant. Landing on all even needs the odd count down to nothing, so the odd count must be even to begin with. Landing on all odd needs it up to the full length, so it must match the length's parity, which is the same as saying the even count is even. When the length is odd exactly one of those two counts is even, so one of the goals is always reachable; when the length is even the two counts share a parity, so it comes down to whether the odd count is even. One pass counting the odd counters settles it.

Pythonentry point: uniform_array

def uniform_array(nums1):
    odd = 0
    for v in nums1:
        if v % 2 == 1:
            odd += 1
    even = len(nums1) - odd
    return odd % 2 == 0 or even % 2 == 0

The obvious version

Search the parities directly. A position is which counters are currently odd, and every nudge of every pair is tried from it, keeping track of the positions already reached, until one turns up with all odd or all even. Exponential in the counter count and it knows nothing about invariants.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_uniform_array(nums1):
    n = len(nums1)
    start = 0
    for i in range(n):
        if nums1[i] % 2 == 1:
            start |= 1 << i
    full = (1 << n) - 1
    seen = set([start])
    queue = [start]
    while queue:
        state = queue.pop()
        if state == 0 or state == full:
            return True
        for i in range(n):
            for j in range(i + 1, n):
                nxt = state ^ (1 << i) ^ (1 << j)
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
    return False

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in