Solve Four Online Assessment Coding Tasks

Problem Statement

Given an array of positive integers nums, you want to partition the entire array into the maximum possible number of contiguous, non-empty subarrays such that every subarray has the exact same element sum.

Return the maximum number of subarrays, k, that nums can be divided into.

Every element of nums must belong to exactly one subarray, and the relative order of elements must be preserved.

Function Signature

def max_equal_sum_partitions(nums: list[int]) -> int:
    pass

Input and Output Format

• Input: A list of positive integers nums of length n.
• Output: An integer representing the maximum number of contiguous segments k where all segments have identical sums.

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• The sum of elements in nums will not exceed 10^9.

Examples

Example 1

Input: nums = [1, 2, 3, 1, 1, 1, 3]
Output: 4
Explanation: 
The total sum is 12. We can partition the array into 4 subarrays of sum 3:
[1, 2], [3], [1, 1, 1], and [3].
No partition into more than 4 subarrays with equal sum is possible.

Example 2

Input: nums = [3, 2, 4, 1]
Output: 2
Explanation:
The total sum is 10. We can partition the array into 2 subarrays of sum 5:
[3, 2] and [4, 1].
It is impossible to partition into more than 2 subarrays of equal sum.

Edge Cases

• nums.length == 1: The only partition is the array itself, so return 1.
• All elements equal: An array like [2, 2, 2, 2] should return 4 (each subarray has size 1).
• Prime total sum: If the total sum is prime, the only possible partitions have sum equal to the total sum (k = 1) or each element equal to 1 (if total sum equals nums.length).