Ways to Make a Fair Array #5 Most Asked
Medium
7 views
Topics:
ArraysDynamic Programming
You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.
For example, if nums = [6,1,7,4,1]:
- Choosing to remove index
1results innums = [6,7,4,1]. - Choosing to remove index
2results innums = [6,1,4,1]. - Choosing to remove index
4results innums = [6,1,7,4].
An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.
Return the number of indices that you could choose such that after the removal, nums is fair.
Example 1:
Input: nums = [2,1,6,4] Output: 1 Explanation: Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair. Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair. Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair. Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair. There is 1 index that you can remove to make nums fair.
Example 2:
Input: nums = [1,1,1] Output: 3 Explanation: You can remove any index and the remaining array is fair.
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: You cannot make a fair array after removing any index.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 104
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of values for the integers in the `nums` array?
- Can the input array `nums` be empty or null?
- What should I return if no index removal results in a fair array?
- Are the integers in the array guaranteed to be whole numbers (integers), or could they be floating point numbers?
- What is the maximum possible length of the `nums` array?
Brute Force Solution
Approach
To solve this problem using brute force, we will explore every possible scenario by systematically removing each number one at a time. We check if removing that number makes the remaining list 'fair' according to the problem's definition.
Here's how the algorithm would work step-by-step:
- First, consider the original list of numbers.
- Then, one by one, remove each number from the list.
- After removing a number, check if the remaining list is 'fair'.
- A list is 'fair' if the sum of the numbers in the even positions equals the sum of the numbers in the odd positions.
- If the remaining list is fair, count that removal as a success.
- Repeat this process of removing and checking for every number in the original list.
- In the end, report the total number of successful removals that resulted in a fair list.
Code Implementation
def ways_to_make_a_fair_array(numbers):
successful_removal_count = 0
for index_to_remove in range(len(numbers)):
modified_numbers = numbers[:index_to_remove] + numbers[index_to_remove+1:]
# Calculate the sum of even and odd indices
even_sum = 0
odd_sum = 0
for index in range(len(modified_numbers)):
if index % 2 == 0:
even_sum += modified_numbers[index]
else:
odd_sum += modified_numbers[index]
# Determine if the array is fair after removing the element.
if even_sum == odd_sum:
successful_removal_count += 1
return successful_removal_countBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it removes the element and then iterates through the remaining elements to calculate the sum of elements at even and odd indices. This inner iteration takes O(n) time. Therefore, the overall time complexity is O(n * n), which simplifies to O(n²).
Space Complexity
O(1) – The brute force solution, as described, operates primarily in place. While it conceptually removes elements one at a time and checks fairness, it doesn't explicitly create a copy of the modified list for each removal. Instead, it calculates the sums based on the original list, skipping the 'removed' index. Therefore, it only needs a few integer variables to store sums and the removed index. This means the auxiliary space used remains constant irrespective of the input size N (the number of elements in the list).
Optimal Solution
Approach
The key insight is that we can compute the sums of even and odd placed numbers without actually removing anything. We'll keep track of these sums and update them as if we removed numbers one by one. This clever precomputation allows us to solve the problem very efficiently.
Here's how the algorithm would work step-by-step:
- First, calculate the sums of all the numbers in even positions and odd positions in the original arrangement.
- Now, think about removing each number, one at a time, and see how it affects the even and odd sums.
- If we hypothetically take out a number from an even position, the numbers to its right will shift over, changing their even/odd status. The even sum will decrease by the value of the number we removed, and the old odd sum will now become the new even sum for the remaining arrangement to the right of the removed number.
- Similarly, if we hypothetically take out a number from an odd position, the odd sum will decrease by the value of the number we removed, and the old even sum will now become the new odd sum for the remaining arrangement to the right of the removed number.
- For each removal, calculate the new even and odd sums of the remaining numbers. If they are equal, that's one way to make the arrangement fair.
- Count all the times the new even and odd sums are equal, after simulating each removal. This count is the total number of ways to make the arrangement fair.
Code Implementation
def ways_to_make_fair(numbers):
even_sum = 0
odd_sum = 0
# Calculate initial even and odd sums.
for i in range(len(numbers)):
if i % 2 == 0:
even_sum += numbers[i]
else:
odd_sum += numbers[i]
ways_to_fair = 0
current_even_sum = 0
current_odd_sum = 0
for i in range(len(numbers)):
if i % 2 == 0:
even_sum -= numbers[i]
else:
odd_sum -= numbers[i]
# Simulate removing the number at index i
if current_even_sum + odd_sum == current_odd_sum + even_sum:
ways_to_fair += 1
# Update current even and odd sums
if i % 2 == 0:
current_even_sum += numbers[i]
else:
current_odd_sum += numbers[i]
return ways_to_fairBig(O) Analysis
Time Complexity
O(n) – The algorithm iterates through the input array nums of size n once. Inside the loop, it performs constant-time operations: updating sums and comparing them. The pre-computation of the initial even and odd sums also takes O(n) time, but since it's a single pass, it does not change the overall complexity. Therefore, the time complexity is directly proportional to the size of the input array, making it O(n).
Space Complexity
O(1) – The algorithm precomputes the sums of even and odd positioned numbers, storing them in a few variables. It then iterates through the input array, updating these sum variables. Since the number of variables used to store sums and the count of fair arrays remains constant regardless of the input array's size (N), the auxiliary space complexity is O(1).
Edge Cases
| Case | How to Handle |
|---|---|
| Null or empty input array | Return 0 as there are no elements to remove and no fair arrays can be created. |
| Array with one element | Return 1, as removing the single element results in an empty array, which is considered fair by definition. |
| Array with two elements | Return 1 if the two elements are equal, otherwise return 0. |
| Array with only even numbers | The algorithm should still correctly calculate sums and determine fairness based on element removal. |
| Array with only odd numbers | The algorithm should still correctly calculate sums and determine fairness based on element removal. |
| Array with large numbers that could cause integer overflow when summing | Use a 64-bit integer type to store sums to prevent overflow. |
| Array with negative numbers | The sum calculations should handle negative numbers correctly; no special handling is needed. |
| Array with alternating large positive and negative numbers such that partial sums fluctuate significantly | Prefix sum calculations should still function correctly as they maintain a running total. |
Null or empty input array
How to Handle:
Return 0 as there are no elements to remove and no fair arrays can be created.
Array with one element
How to Handle:
Return 1, as removing the single element results in an empty array, which is considered fair by definition.
Array with two elements
How to Handle:
Return 1 if the two elements are equal, otherwise return 0.
Array with only even numbers
How to Handle:
The algorithm should still correctly calculate sums and determine fairness based on element removal.
Array with only odd numbers
How to Handle:
The algorithm should still correctly calculate sums and determine fairness based on element removal.
Array with large numbers that could cause integer overflow when summing
How to Handle:
Use a 64-bit integer type to store sums to prevent overflow.
Array with negative numbers
How to Handle:
The sum calculations should handle negative numbers correctly; no special handling is needed.
Array with alternating large positive and negative numbers such that partial sums fluctuate significantly
How to Handle:
Prefix sum calculations should still function correctly as they maintain a running total.
0/0 Twilio questions completed
0/0 completed
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
