LeetCode 1664: Ways to Make a Fair Array
Problem Description
Explanation
To solve this problem, we need to iterate through each index in the array and check if removing that index would make the array fair. We can do this by calculating the sums of even-indexed and odd-indexed elements before and after removing each index. If the sums are equal, we increment a counter. Finally, we return the counter as the result.
-
Algorithm:
- Initialize variables for the total sum, even sum, odd sum, and count of fair indices.
- Calculate the initial total sum, even sum, and odd sum of the array.
- Iterate through each index in the array.
- For each index, calculate the total sum, even sum, and odd sum after removing that index.
- If the even sum and odd sum are equal, increment the count of fair indices.
- Return the count as the result.
-
Time Complexity: O(n) where n is the length of the input array.
-
Space Complexity: O(1)
Solutions
class Solution {
public int waysToMakeFair(int[] nums) {
int n = nums.length;
int totalSum = 0, evenSum = 0, oddSum = 0, count = 0;
for (int num : nums) {
totalSum += num;
}
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
evenSum += nums[i];
} else {
oddSum += nums[i];
}
}
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
evenSum -= nums[i];
} else {
oddSum -= nums[i];
}
if (evenSum + oddSum == totalSum - nums[i]) {
count++;
}
if (i % 2 == 0) {
evenSum += nums[i];
} else {
oddSum += nums[i];
}
}
return count;
}
}Loading editor...