Ways to Make a Fair Array
Medium About 20 min Free, no account needed
Count the removals that leave odd and even index sums equal.
The brief
Given an integer array nums, you may remove exactly one element. After a
removal the elements to its right shift left, so their index parity flips.
The array is fair when the sum of values at even indices equals the sum at
odd indices. Count how many removal indices produce a fair array.
The obvious approach materializes the array-after-removal for every index, O(n2). The hidden test has 200,000 elements, so it's too slow. You need O(1) work per candidate index for an O(n) total, which means each removal cannot rebuild or rescan the array.
Starter code
using System;
public class Solution
{
// TODO: return the count of indices whose removal leaves even- and odd-indexed sums equal.
public int WaysToMakeFair(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Prefix sums
- Carry running totals or prefix state so any range question becomes a lookup.
Related katas
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- Product of Array Except Self Medium Free For each index, return the product of all other elements, without division.
- Subarray Sum Equals K Medium Free Count contiguous subarrays whose elements sum to a target k.
- Subarrays Divisible by K Medium Free Count the subarrays whose sum is divisible by k.