Tug Of War Minimum Difference
01 · Problem
You are given an integer array nums of length n. Divide its elements into two teams so that every element belongs to exactly one team and the team sizes differ by at most one: when n is even both teams have n / 2 elements; when n is odd one team has (n - 1) / 2 elements and the other has (n + 1) / 2.
Return the smallest possible absolute difference between the two teams' sums. When n = 1, one team is empty (sum 0).
02 · Examples
nums = [3,4,5,-3,100,1,89,54,23,20]
0
The teams {4,100,1,23,20} and {3,5,-3,89,54} each have five elements and both sum to 148.
nums = [1,2,3]
0
With three elements the teams have sizes 1 and 2. Choosing {3} and {1,2} gives sums 3 and 3.
nums = [10,20]
10
Each team gets one element, so the difference is |10 - 20| = 10.
03 · Constraints
- 01`1 <= nums.length <= 20`
- 02`-1000 <= nums[i] <= 1000`
- 03Team sizes must differ by at most 1
04 · Optimal complexity
- Time
- O(C(n, n/2))
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.