Count deletions making array fair
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 1664. Ways to Make a Fair Array – Given an integer array nums, count the indices whose removal results in the sum of elements at even indices equaling the sum at odd indices (k =
1). Follow-up: extend the algorithm to count ways after deleting exactly k elements.
https://leetcode.com/problems/ways-to-make-a-fair-array/description/
Quick Answer: This question evaluates proficiency with array manipulation, parity-aware summation, and combinatorial counting when elements are removed, situating it in the Coding & Algorithms domain.
Given a 0-indexed integer array nums, return the number of indices i such that removing nums[i] and re-indexing the remaining elements from 0 makes the sum of elements at even indices equal to the sum of elements at odd indices. An empty array has both sums equal to 0.
Constraints
- 1 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- Use 64-bit integer arithmetic for sums
- Target time complexity: O(n)
- Target extra space: O(1)
Hints
- Compute total sums at even and odd indices once.
- Scan left-to-right maintaining prefix sums left_even and left_odd.
- When removing index i, the suffix elements shift left by one, flipping their parity. New even sum = left_even + suffix_odd; new odd sum = left_odd + suffix_even.