Skip to content

3467. Transform Array by Parity

SourceBiweekly Contest 151 Q1DifficultyEasyRating1165

Description

You are given an integer array nums. Transform nums by performing the following operations in the exact order specified:

  1. Replace each even number with 0.
  2. Replace each odd numbers with 1.
  3. Sort the modified array in non-decreasing order.

Return the resulting array after performing these operations.

 

Example 1:

Input: nums = [4,3,2,1]

Output: [0,0,1,1]

Explanation:

  • Replace the even numbers (4 and 2) with 0 and the odd numbers (3 and 1) with 1. Now, nums = [0, 1, 0, 1].
  • After sorting nums in non-descending order, nums = [0, 0, 1, 1].

Example 2:

Input: nums = [1,5,1,4,2]

Output: [0,0,1,1,1]

Explanation:

  • Replace the even numbers (4 and 2) with 0 and the odd numbers (1, 5 and 1) with 1. Now, nums = [1, 1, 1, 0, 0].
  • After sorting nums in non-descending order, nums = [0, 0, 1, 1, 1].

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 1000

Solutions

Solution 1: Counting

Thinking

Evens become \(0\), odds become \(1\), then the array is sorted non-decreasing. That is just all zeros in front. \(n\le 100\), so a count suffices.

No sort is required: the even count \(\textit{even}\) is the length of the zero prefix.

Count evens in one pass and write the two segments back.

We can traverse the array \(\textit{nums}\) and count the number of even elements \(\textit{even}\). Then, we set the first \(\textit{even}\) elements of the array to \(0\) and the remaining elements to \(1\).

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

1
2
3
4
5
6
7
8
class Solution:
    def transformArray(self, nums: List[int]) -> List[int]:
        even = sum(x % 2 == 0 for x in nums)
        for i in range(even):
            nums[i] = 0
        for i in range(even, len(nums)):
            nums[i] = 1
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int[] transformArray(int[] nums) {
        int even = 0;
        for (int x : nums) {
            even += (x & 1 ^ 1);
        }
        for (int i = 0; i < even; ++i) {
            nums[i] = 0;
        }
        for (int i = even; i < nums.length; ++i) {
            nums[i] = 1;
        }
        return nums;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> transformArray(vector<int>& nums) {
        int even = 0;
        for (int x : nums) {
            even += (x & 1 ^ 1);
        }
        for (int i = 0; i < even; ++i) {
            nums[i] = 0;
        }
        for (int i = even; i < nums.size(); ++i) {
            nums[i] = 1;
        }
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func transformArray(nums []int) []int {
    even := 0
    for _, x := range nums {
        even += x&1 ^ 1
    }
    for i := 0; i < even; i++ {
        nums[i] = 0
    }
    for i := even; i < len(nums); i++ {
        nums[i] = 1
    }
    return nums
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function transformArray(nums: number[]): number[] {
    const even = nums.filter(x => x % 2 === 0).length;
    for (let i = 0; i < even; ++i) {
        nums[i] = 0;
    }
    for (let i = even; i < nums.length; ++i) {
        nums[i] = 1;
    }
    return nums;
}

Comments