Welcome to Subscribe On Youtube
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 bothnums[i]
andnums[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 bothnums[1]
andnums[2]
by -1. Nownums = [1,1,-1,-1,1]
. - Choose index
i = 2
, and multiply bothnums[2]
andnums[3]
by -1. Nownums = [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)$.
-
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); } };
-
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)
-
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) } }