Skip to content

3876. Construct Uniform Parity Array II

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, such that nums1[i] - nums1[j] >= 1

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

Β 

Example 1:

Input: nums1 = [1,4,7]

Output: true

Explanation:​​​​​​​​​​​​​​

  • Set nums2[0] = nums1[0] = 1.
  • Set nums2[1] = nums1[1] - nums1[0] = 4 - 1 = 3.
  • Set nums2[2] = nums1[2] = 7.
  • nums2 = [1, 3, 7], and all elements are odd. Thus, the answer is true.

Example 2:

Input: nums1 = [2,3]

Output: false

Explanation:

It is not possible to construct nums2 such that all elements have the same parity. Thus, the answer is false.

Example 3:

Input: nums1 = [4,6]

Output: true

Explanation:

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

Β 

Constraints:

  • 1 <= n == nums1.length <= 105
  • 1 <= nums1[i] <= 109
  • 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 need to find the minimum odd number \(mn\), and check whether there exists an even number \(x\) in \(\textit{nums1}\) such that \(x < mn\). If such an even number exists, we cannot construct a valid \(\textit{nums2}\), so we return \(\text{false}\); otherwise we return \(\text{true}\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums1}\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        mn = inf
        for x in nums1:
            if x % 2:
                mn = min(mn, x)
        for x in nums1:
            if x % 2 == 0 and mn != inf and x < mn:
                return False
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public boolean uniformArray(int[] nums1) {
        final int inf = Integer.MAX_VALUE;
        int mn = inf;
        for (int x : nums1) {
            if (x % 2 == 1) {
                mn = Math.min(mn, x);
            }
        }
        for (int x : nums1) {
            if (x % 2 == 0 && mn != inf && x < mn) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool uniformArray(vector<int>& nums1) {
        int mn = INT_MAX;
        for (int x : nums1) {
            if (x % 2 == 1) {
                mn = min(mn, x);
            }
        }
        for (int x : nums1) {
            if (x % 2 == 0 && mn != INT_MAX && x < mn) {
                return false;
            }
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func uniformArray(nums1 []int) bool {
    mn := int(^uint(0) >> 1)
    for _, x := range nums1 {
        if x%2 == 1 && x < mn {
            mn = x
        }
    }
    for _, x := range nums1 {
        if x%2 == 0 && mn != int(^uint(0)>>1) && x < mn {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function uniformArray(nums1: number[]): boolean {
    let mn = Number.MAX_SAFE_INTEGER;
    for (const x of nums1) {
        if (x % 2 === 1) {
            mn = Math.min(mn, x);
        }
    }
    for (const x of nums1) {
        if (x % 2 === 0 && mn !== Number.MAX_SAFE_INTEGER && x < mn) {
            return false;
        }
    }
    return true;
}

Comments