Skip to content

3875. Construct Uniform Parity Array I

Description

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.

Β 

Example 1:

Input: nums1 = [2,3]

Output: true

Explanation:

  • Choose nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1.
  • Choose nums2[1] = nums1[1] = 3.
  • nums2 = [-1, 3], and both elements are odd. Thus, the answer is true​​​​​​​.

Example 2:

Input: nums1 = [4,6]

Output: true

Explanation:​​​​​​​

  • Choose nums2[0] = nums1[0] = 4.
  • Choose nums2[1] = nums1[1] = 6.
  • nums2 = [4, 6], and all elements are even. Thus, the answer is true.

Β 

Constraints:

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

Solutions

Solution 1: Brain Teaser

If all elements in \(\textit{nums1}\) are either all odd or all even, we can directly set \(\textit{nums2}\) equal to \(\textit{nums1}\), which satisfies the condition.

If \(\textit{nums1}\) contains both odd and even numbers, we can set each element of \(\textit{nums2}\) to the current element of \(\textit{nums1}\) minus some element in \(\textit{nums1}\) with different parity. Since odd minus even and even minus odd both yield an odd number, all elements of \(\textit{nums2}\) will be odd, satisfying the condition.

Therefore, regardless of whether the elements in \(\textit{nums1}\) are all odd, all even, or a mix of both, we can always construct a valid \(\textit{nums2}\). Thus the answer is always \(\text{true}\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

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

1
2
3
4
5
class Solution {
    public boolean uniformArray(int[] nums1) {
        return true;
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        return true;
    }
};

1
2
3
func uniformArray(nums1 []int) bool {
    return true
}

1
2
3
function uniformArray(nums1: number[]): boolean {
    return true;
}

Comments