We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ways to Make a Fair Array

Number: 1783

Difficulty: Medium

Paid? No

Companies: DoorDash, Twilio, Nvidia, Dunzo

Problem Description

Given an integer array, remove exactly one index so that after removal the sum of the even-indexed elements equals the sum of the odd-indexed elements (i.e. the array becomes "fair"). Return the count of all such indices where removal makes the array fair.

Key Insights

  • Removal of an element shifts the indices of all subsequent elements, affecting their parity (even/odd positions).
  • Precompute the total sums of even-indexed and odd-indexed elements.
  • Use prefix sums (left sums) to maintain cumulative sums and derive right sums by subtracting from the totals.
  • Depending on whether the removed index is even or odd, the right portion of the array will have its elements’ parity flipped.
  • A single pass O(n) solution is possible by updating prefix sums on the fly.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (only a few extra integer variables are used)

Solution

The solution iterates over each index and simulates the removal of the element at that index, then calculates the resulting sums for even and odd positions:

  1. Compute the total sum of elements at even indices (total_even) and at odd indices (total_odd).
  2. Initialize prefix sums (left_even and left_odd) for elements before the current index.
  3. For each index i:
    • If i is even:
      • The new even sum becomes: left_even + (total_odd - left_odd)
      • The new odd sum becomes: left_odd + (total_even - left_even - nums[i])
    • If i is odd:
      • The new even sum becomes: left_even + (total_odd - left_odd - nums[i])
      • The new odd sum becomes: left_odd + (total_even - left_even)
  4. If the new even sum equals the new odd sum, the removal of index i yields a fair array.
  5. Update the left prefix sums with nums[i] by checking its parity. This approach only requires one pass over the array, ensuring an efficient solution.

Code Solutions

# Python solution with detailed comments

def waysToMakeFair(nums):
    # Calculate total sums for even and odd indices
    total_even, total_odd = 0, 0
    for i, num in enumerate(nums):
        if i % 2 == 0:
            total_even += num
        else:
            total_odd += num

    left_even, left_odd = 0, 0  # Prefix sums for even and odd parts before the current index
    fair_count = 0  # Count of indices that yield a fair array

    # Traverse the array and simulate removal of each element
    for i, num in enumerate(nums):
        # Remove current element and calculate new sums for the right part
        if i % 2 == 0:
            # For even index removal:
            # New even sum = left_even + right odd sum (total_odd - left_odd)
            # New odd sum  = left_odd + right even sum (total_even - left_even - num)
            new_even = left_even + (total_odd - left_odd)
            new_odd = left_odd + (total_even - left_even - num)
        else:
            # For odd index removal:
            # New even sum = left_even + right odd sum (total_odd - left_odd - num)
            # New odd sum  = left_odd + right even sum (total_even - left_even)
            new_even = left_even + (total_odd - left_odd - num)
            new_odd = left_odd + (total_even - left_even)

        # Check if the resulting array is fair
        if new_even == new_odd:
            fair_count += 1

        # Update prefix sums based on the current element's index parity
        if i % 2 == 0:
            left_even += num
        else:
            left_odd += num

    return fair_count

# Example usage:
if __name__ == "__main__":
    print(waysToMakeFair([2,1,6,4]))  # Output: 1
← Back to All Questions