Minimize reduction cost and validate equal-sum pairs
Company: MathWorks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two independent coding tasks.
## Task 1: Minimum total cost to reduce an array
You are given an integer array `arr` of length `n`.
You may repeatedly perform the following **reduction** operation until only one number remains:
1. Choose any two elements `x` and `y` currently in the array.
2. Remove both from the array.
3. Insert their sum `x + y` back into the array.
4. The **cost** of this operation is `x + y`.
Return the **minimum possible total cost** over all sequences of operations.
**Input:** `arr` (integers)
**Output:** minimum total cost (use 64-bit integer)
**Notes/assumptions (make explicit in your solution):**
- `n >= 1`.
- Elements can be any integers; total cost should be computed using 64-bit arithmetic.
---
## Task 2: Pair elements into equal-sum groups and sum products
You are given an integer array `arr` of **even** length `2m`.
You must partition the array into `m` disjoint pairs such that:
- Every element is used in exactly one pair.
- The **sum of the two numbers in each pair is the same constant** `S` for all pairs.
If such a partition is possible, return:
- The value \(\sum_{i=1}^{m} (a_i \times b_i)\), i.e., the **sum of products** of each pair.
If it is **not** possible to form such pairs, return `-1`.
**Input:** `arr` (even length)
**Output:** sum of pairwise products, or `-1` (use 64-bit integer)
Quick Answer: This two-part question evaluates array manipulation and algorithmic problem-solving skills: the first task focuses on optimizing cumulative operation costs during iterative reductions while the second assesses combinatorial pairing under equal-sum constraints and computation of aggregate pairwise products.
Minimum Reduction Cost
Repeatedly merge two numbers at cost x+y and return the minimum total cost.
Constraints
- Use 64-bit arithmetic for large values
Examples
Input: ([1, 2, 3],)
Expected Output: 9
Explanation: Merge 1+2 then 3+3.
Input: ([5],)
Expected Output: 0
Explanation: No operation.
Input: ([-5, 1, 2],)
Expected Output: -6
Explanation: Handles negative values deterministically.
Input: ([4, 3, 2, 6],)
Expected Output: 29
Explanation: Huffman-style merge.
Hints
- Always merge the two smallest current values.
Equal-Sum Pair Products
Pair all elements so every pair has the same sum and return the sum of products, or -1 if impossible.
Constraints
- arr has even length for valid pairing
Examples
Input: ([3, 2, 5, 4],)
Expected Output: 22
Explanation: Pairs sum to 7.
Input: ([1, 1, 2, 3],)
Expected Output: -1
Explanation: Impossible.
Input: ([1, 2, 2, 3],)
Expected Output: 7
Explanation: Two equal-sum pairs.
Input: ([-1, 4, 0, 3],)
Expected Output: -4
Explanation: Negative values.
Hints
- Sort and pair smallest with largest; all pairs must match the first sum.