Is Construct Uniform Parity Array I easy or hard?

Construct Uniform Parity Array I is classified as an Easy problem. The challenge mainly involves recognizing the parity constraint and constructing the array accordingly. Once you apply simple modulo logic and iteration, the implementation becomes straightforward.

Construct Uniform Parity Array I Python/Java solution

The implementation is straightforward in Python, Java, C++, Go, or TypeScript. Iterate through the array length and assign values that maintain consistent parity, typically by starting with a valid number and increasing by 2 each step. This preserves the parity constraint and keeps the algorithm O(n).

How to solve Construct Uniform Parity Array I in O(n)?

Determine the parity you want all elements to share. Then iterate from index 0 to n-1 and assign values that maintain that parity, such as increasing by 2 or adjusting numbers so value % 2 remains consistent. Since each position is processed once, the algorithm runs in linear time.

What is the best approach for Construct Uniform Parity Array I?

The best approach is a direct parity construction. Choose a target parity (even or odd) and generate elements that maintain that parity while filling the array. This requires a single pass over the array and simple arithmetic checks like value % 2. The complexity is O(n) time and O(1) extra space.

Is Construct Uniform Parity Array I asked at Google/Amazon/Meta?

Parity and array construction problems frequently appear in screening rounds at large companies because they test logical reasoning and edge-case handling. While this exact problem may vary by platform, similar parity-based array construction tasks are common in coding interviews.

What data structure is used in Construct Uniform Parity Array I?

The problem primarily uses a basic array for output construction. No complex data structures such as hash maps or trees are required. The logic focuses on arithmetic parity checks and sequential iteration.

What is the time complexity of Construct Uniform Parity Array I?

The optimal solution runs in O(n) time because you iterate through the array once to assign values with the required parity. Each step performs constant-time operations such as arithmetic and parity checks. Space complexity is O(1) beyond the output array.

Description Hints 1 Solution Video 3:39

3875. Construct Uniform Parity Array I

Easy85.8% acceptance2 companies

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.

Asked at 2 companies

Amdocs

Google

Topics

Array Math

Hints open one at a time

Hint 1

There is only one possible answer.

3:39

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

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

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,3]

Input

[4,6]

Your code is saved on this device.Solution