3576. Transform Array to All Equal Elements

Description

You are given an integer array nums of size n containing only 1 and -1, and an integer k.

You can perform the following operation at most k times:

• Choose an index i (0 <= i < n - 1), and multiply both nums[i] and nums[i + 1] by -1.

Note that you can choose the same index i more than once in different operations.

Return true if it is possible to make all elements of the array equal after at most k operations, and false otherwise.

 

Example 1:

Input: nums = [1,-1,1,-1,1], k = 3

Output: true

Explanation:

We can make all elements in the array equal in 2 operations as follows:

• Choose index i = 1, and multiply both nums[1] and nums[2] by -1. Now nums = [1,1,-1,-1,1].
• Choose index i = 2, and multiply both nums[2] and nums[3] by -1. Now nums = [1,1,1,1,1].

Example 2:

Input: nums = [-1,-1,-1,1,1,1], k = 5

Output: false

Explanation:

It is not possible to make all array elements equal in at most 5 operations.

 

Constraints:

• 1 <= n == nums.length <= 105
• nums[i] is either -1 or 1.
• 1 <= k <= n

Solutions

Solution 1: Traversal and Counting

According to the problem description, to make all elements in the array equal, all elements must be either \(\textit{nums}[0]\) or \(-\textit{nums}[0]\). Therefore, we design a function \(\textit{check}\) to determine whether the array can be transformed into all elements equal to \(\textit{target}\) with at most \(k\) operations.

The idea of this function is to traverse the array and count the number of operations needed. Each element is either modified once or not at all. If the current element is equal to the target value, no modification is needed and we continue to the next element. If the current element is not equal to the target value, an operation is needed, increment the counter, and flip the sign, indicating that subsequent elements need the opposite operation.

After the traversal, if the counter is less than or equal to \(k\) and the sign of the last element matches the target value, return \(\textit{true}\); otherwise, return \(\textit{false}\).

The final answer is the result of \(\textit{check}(\textit{nums}[0], k)\) or \(\textit{check}(-\textit{nums}[0], k)\).

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

Python3JavaC++GoTypeScriptRust

class Solution:
    def canMakeEqual(self, nums: List[int], k: int) -> bool:
        def check(target: int, k: int) -> bool:
            cnt, sign = 0, 1
            for i in range(len(nums) - 1):
                x = nums[i] * sign
                if x == target:
                    sign = 1
                else:
                    sign = -1
                    cnt += 1
            return cnt <= k and nums[-1] * sign == target

        return check(nums[0], k) or check(-nums[0], k)

class Solution {
    public boolean canMakeEqual(int[] nums, int k) {
        return check(nums, nums[0], k) || check(nums, -nums[0], k);
    }

    private boolean check(int[] nums, int target, int k) {
        int cnt = 0, sign = 1;
        for (int i = 0; i < nums.length - 1; ++i) {
            int x = nums[i] * sign;
            if (x == target) {
                sign = 1;
            } else {
                sign = -1;
                ++cnt;
            }
        }
        return cnt <= k && nums[nums.length - 1] * sign == target;
    }
}

class Solution {
public:
    bool canMakeEqual(vector<int>& nums, int k) {
        auto check = [&](int target, int k) -> bool {
            int n = nums.size();
            int cnt = 0, sign = 1;
            for (int i = 0; i < n - 1; ++i) {
                int x = nums[i] * sign;
                if (x == target) {
                    sign = 1;
                } else {
                    sign = -1;
                    ++cnt;
                }
            }
            return cnt <= k && nums[n - 1] * sign == target;
        };
        return check(nums[0], k) || check(-nums[0], k);
    }
};

func canMakeEqual(nums []int, k int) bool {
    check := func(target, k int) bool {
        cnt, sign := 0, 1
        for i := 0; i < len(nums)-1; i++ {
            x := nums[i] * sign
            if x == target {
                sign = 1
            } else {
                sign = -1
                cnt++
            }
        }
        return cnt <= k && nums[len(nums)-1]*sign == target
    }
    return check(nums[0], k) || check(-nums[0], k)
}

function canMakeEqual(nums: number[], k: number): boolean {
    function check(target: number, k: number): boolean {
        let [cnt, sign] = [0, 1];
        for (let i = 0; i < nums.length - 1; i++) {
            const x = nums[i] * sign;
            if (x === target) {
                sign = 1;
            } else {
                sign = -1;
                cnt++;
            }
        }
        return cnt <= k && nums[nums.length - 1] * sign === target;
    }

    return check(nums[0], k) || check(-nums[0], k);
}

impl Solution {
    pub fn can_make_equal(nums: Vec<i32>, k: i32) -> bool {
        fn check(target: i32, k: i32, nums: &Vec<i32>) -> bool {
            let mut cnt = 0;
            let mut sign = 1;
            for i in 0..nums.len() - 1 {
                let x = nums[i] * sign;
                if x == target {
                    sign = 1;
                } else {
                    sign = -1;
                    cnt += 1;
                }
            }
            cnt <= k && nums[nums.len() - 1] * sign == target
        }

        check(nums[0], k, &nums) || check(-nums[0], k, &nums)
    }
}

Comments