Maximize Equal Array Length After Contiguous Sum Merges

Quick Overview

Find the maximum length of equal arrays obtainable by merging adjacent positive values into their sums, or report that equality is impossible.

Maximize Equal Array Length After Contiguous Sum Merges

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two nonempty arrays of positive integers, `a` and `b`. In either array, you may replace a contiguous group of elements with one element equal to their sum. You may repeat this operation independently on both arrays. Implement `maxCommonLength(a, b)`. Return the maximum possible length of the resulting arrays when they are exactly equal, element by element. Return `-1` if they cannot be made equal. ### Rules and Constraints - Merging preserves element order. You may merge adjacent groups but cannot split an element, reorder elements, or remove values. - You may perform no operations on an array that already has the desired form. - Each array has between 1 and 100,000 elements. Every value is between 1 and 1,000,000,000. - Intermediate and total sums must be represented exactly. ### Example 1 ```text a = [1, 2, 3, 3] b = [3, 3, 3] Output: 3 ``` Merge the first two elements of `a` to obtain `[3, 3, 3]`. Length 3 is maximal because `b` starts with only three elements and merging cannot increase its length. ### Example 2 ```text a = [1, 2] b = [4] Output: -1 ``` No allowed sequence of merges makes these arrays equal.

Overview: Find the maximum length of equal arrays obtainable by merging adjacent positive values into their sums, or report that equality is impossible.

|Home/Coding & Algorithms/Microsoft
Microsoft logo
Microsoft
Sep 5, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

You are given two nonempty arrays of positive integers, a and b. In either array, you may replace a contiguous group of elements with one element equal to their sum. You may repeat this operation independently on both arrays.

Implement maxCommonLength(a, b). Return the maximum possible length of the resulting arrays when they are exactly equal, element by element. Return -1 if they cannot be made equal.

Rules and Constraints

  • Merging preserves element order. You may merge adjacent groups but cannot split an element, reorder elements, or remove values.
  • You may perform no operations on an array that already has the desired form.
  • Each array has between 1 and 100,000 elements. Every value is between 1 and 1,000,000,000.
  • Intermediate and total sums must be represented exactly.

Example 1

 a = [1, 2, 3, 3]
 b = [3, 3, 3]
Output: 3

Merge the first two elements of a to obtain [3, 3, 3]. Length 3 is maximal because b starts with only three elements and merging cannot increase its length.

Example 2

 a = [1, 2]
 b = [4]
Output: -1

No allowed sequence of merges makes these arrays equal.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...