Welcome to Subscribe On Youtube

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

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


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


  • 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


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


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

All Problems

All Solutions