Problem

You are given an array nums1 of n distinct integers.

You want to construct another array nums2 of length n such that the elements in nums2 are either all odd or all even.

For each index i, you must choose exactly one of the following (in any order):

• nums2[i] = nums1[i]
• nums2[i] = nums1[i] - nums1[j], for an index j != i

Return true if it is possible to construct such an array, otherwise return false.

Constraints:

• 1 <= n == nums1.length <= 100
• 1 <= nums1[i] <= 100
• nums1 consists of distinct integers.

Examples:

• nums1 = [2, 3] → true. Pick nums2[0] = 2 - 3 = -1 (odd) and nums2[1] = 3 (odd).
• nums1 = [4, 6] → true. Keep both as-is; [4, 6] is all even.

Walkthrough

Problem analysis

This isn't a problem where I'd reach for brute force first. Instead I would be thinking about the possible initial array states. We know that nums1 contains distinct positive integers between 1 and 100 inclusive. Our target is to make them all odd or even. We have a rule that says we can just copy a number from nums1 to nums2 which means if they're already all even or odd we can copy them and be done.

If they aren't all even or odd then that means there are both even and odd numbers. We know here we can't just copy them as that wouldn't work. But we can use the subtraction operation. They disallow subtracting the same number from itself, if that was allowed you'd always be able to get 0 and it would be trivially True all the time. Instead we have these possibilities:

• even - even => even
• even - odd => odd
• odd - odd => even
• odd - even => odd

Constructing a solution

So, what does this tell us? There are two possibilities that we can aim for: all even, or all odd. Are these both equally valid? This is where the logic in the problem comes into play. From that table it feels like you can convert both, so maybe it doesn't matter. That's of course a leading question: it very much does.

Converting all the odd elements to even requires you to have two odd values so we can do odd - odd. As you cannot subtract the number from itself if you only have one odd number then no matter what you do with all the other even numbers you can never turn it even. So, converting all to even doesn't work for every array.

Let's instead consider converting everything to odd. So long as there is a single odd value we can convert all the even numbers to odd. Then all the odd numbers can just be copied across.

This means we have:

• Everything is even => True
• Everything is odd => True
• Mixture => Convert all to odd => True

Which means no matter what the input we can always do this!

Remember, it's not asking us to actually construct the array. Just return if it's possible. And we've just determined it's always possible... So, let's just return True!

Solution

1
2
3

class Solution:
  def uniformArray(self, nums1: list[int]) -> bool:
    return True

Submission result