Fewest Adjacent-Sum Merges to Turn an Array Into a Palindrome
Company: Arista Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array of positive integers. In one operation, you choose two adjacent elements and replace them with a single element equal to their sum, so the array becomes one element shorter. Return the minimum number of operations needed to make the array a palindrome: an array that reads the same from left to right as from right to left.
The report did not state value ranges; this version uses positive integers.
### Function Signature
```python
def min_merges_to_palindrome(nums: list[int]) -> int:
```
### Rules
- Each operation merges exactly two adjacent elements of the current array into one element holding their sum.
- An array with a single element is a palindrome, so an answer always exists, and it is at most `len(nums) - 1`.
- Return `0` when `nums` is already a palindrome.
### Constraints
- `1 <= len(nums) <= 10^5`
- `1 <= nums[i] <= 10^9`
- Merged values can reach `10^14`, beyond the 32-bit signed maximum `2^31 - 1`, so use 64-bit integers. They stay well below `2^53`.
### Examples
**Example 1**
```text
Input: nums = [3, 2, 1, 6]
Output: 2
```
Merging `3` and `2`, then `5` and `1`, gives `[6, 6]`. One merge is not enough: the three possible results `[5, 1, 6]`, `[3, 3, 6]` and `[3, 2, 7]` are not palindromes.
**Example 2**
```text
Input: nums = [1, 1, 2, 1, 1, 1]
Output: 1
```
Merging the `2` with the `1` to its right gives `[1, 1, 3, 1, 1]`.
**Example 3**
```text
Input: nums = [4, 2, 4]
Output: 0
```
The array is already a palindrome.
Overview: Given an array of positive integers, find the fewest operations that turn it into a palindrome when each operation replaces two adjacent elements with their sum. The problem tests reasoning about how the two ends of the array must come to match and careful handling of large merged values.
Read the full Arista Networks Software Engineer interview experience this question came from
You are given an array `nums` of positive integers. In one operation, you choose two adjacent elements and replace them with a single element equal to their sum, so the array becomes one element shorter.
Return the minimum number of operations needed to make the array a palindrome: an array that reads the same from left to right as from right to left.
- Each operation merges exactly two adjacent elements of the current array into one element holding their sum.
- An array with a single element is a palindrome, so an answer always exists, and it is at most `len(nums) - 1`.
- Return `0` when `nums` is already a palindrome.
Merged values can reach `10^14`, beyond the 32-bit signed maximum `2^31 - 1`, so use 64-bit integers for sums (`long` in Java, `long long` in C++). They stay well below `2^53`. The returned count is at most `len(nums) - 1` and fits in a 32-bit integer.
**Example 1**
```text
Input: nums = [3, 2, 1, 6]
Output: 2
```
Merging `3` and `2`, then `5` and `1`, gives `[6, 6]`. One merge is not enough: the three possible results `[5, 1, 6]`, `[3, 3, 6]` and `[3, 2, 7]` are not palindromes.
**Example 2**
```text
Input: nums = [1, 1, 2, 1, 1, 1]
Output: 1
```
Merging the `2` with the `1` to its right gives `[1, 1, 3, 1, 1]`.
**Constraints**
- `1 <= len(nums) <= 10^5`
- `1 <= nums[i] <= 10^9`
- Merged values can reach `10^14` (above `2^31 - 1`, below `2^53`).
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^9
- Merged values can reach 10^14, beyond the 32-bit signed maximum 2^31 - 1, so use 64-bit integers for sums (long in Java, long long in C++); they stay well below 2^53.
Examples
Input: ([7],)
Expected Output: 0
Explanation: Minimum valid input: a single element is already a palindrome.
Input: ([5, 5],)
Expected Output: 0
Explanation: Two equal elements already form a palindrome.
Hints
- Every element of the final array is the sum of a contiguous block of the original array, so the number of operations equals the original length minus the number of blocks.
- The first and last elements of the final array must be equal. Compare what can be built starting from the left end with what can be built starting from the right end.
- Merged values can exceed 2^31 - 1, so keep any running totals in 64-bit integers.