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

Thinking

As in part I, except the difference must be positive. An all-same-parity array may still be copied.

To obtain all odds we must subtract a larger opposite-parity value. If the smallest odd is less than some even, that even cannot become a positive odd difference, nor stay even while the rest become odd.

Hence existence of an even smaller than the minimal odd fails; otherwise a construction exists.

If there is no odd, the array is already all even and succeeds.

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)\).

Similar problems:

1
2
3
4
class Solution:
    def uniformArray(self, nums1: List[int]) -> bool:
        mn = min((x for x in nums1 if x & 1), default=None)
        return mn is None or all(x >= mn for x in nums1 if x & 1 == 0)

 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;
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn uniform_array(nums1: Vec<i32>) -> bool {
        match nums1.iter().filter(|&&x| x % 2 == 1).min() {
            None => true,
            Some(&mn) => !nums1.iter().any(|&x| x % 2 == 0 && x < mn),
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public bool UniformArray(int[] nums1) {
        int mn = int.MaxValue;
        foreach (int x in nums1) {
            if (x % 2 == 1) {
                mn = Math.Min(mn, x);
            }
        }
        if (mn == int.MaxValue) {
            return true;
        }
        foreach (int x in nums1) {
            if (x % 2 == 0 && x < mn) {
                return false;
            }
        }
        return true;
    }
}

Comments