Minimum steps needed to make all elements equal by adding adjacent elements

user_14977515 0
Viewed 1644

I have an array A of size N. All elements are positive integers. In one step, I can add two adjacent elements and replace them with their sum. That said, the array size reduces by 1. Now I need to make all the elements same by performing minimum number of steps.

For example: A = [1,2,3,2,1,3].

Step 1: Merge index 0 and 1 ==> A = [3,3,2,1,3]

Step 2: Merge index 2 and 3 (of new array) ==> [3,3,3,3]

Hence number of steps are 2.

I couldn't think of a straight solution, so tried a recursive approach by merging all indices one by one and returning the min level I can get when either array size is 1 or all elements are equal.

Below is the code I tried:

# Checks if all the elements are same or not
def check(A):
    if len(set(A)) == 1:
        return True
    return False

# Recursive function to find min steps
def min_steps(N,A,level):
    # If all are equal return the level
    if N == 1 or check(A):
        return level
    
    # Initialize min variable
    mn = float('+inf')
    # Try merging all one by one and recur
    for i in range(N-1):
        temp = A[:]
        temp[i]+=temp[i+1]
        temp.pop(i+1)
        mn = min(mn, min_steps(N-1,temp, level+1))
    return mn

This solution has complexity of O(N^N). I want to reduce it to polynomial time near to O(N^2) or O(N^3). Can anyone help me modify this solution or tell me if I am missing something?

backtracking dynamic-programming recursion python-3.x arrays
1 Answers

Combining any k adjacent pairs of elements (even if they include elements formed from previous combining steps) leaves exactly n-k elements in total, each of which we can map back to the contiguous subarray of the original problem that constitutes the elements that were added together to form it. So, this problem is equivalent to partitioning the array into the largest possible number of contiguous subarrays such that all subarrays have the same sum: Any adjacent pair of elements within the same subarray can be combined into a single element, and this process repeated within the subarray with adjacent pairs chosen in any order, until all elements have been combined into a single element.

So, if there are n elements and they sum to T, then a simple O(nT) algorithm is:

  1. For i from 0 to T:
    • Try partitioning the elements into subarrays each having sum i. This amounts to scanning along the array, greedily adding the current element to the current subarray if the sum of elements in the current subarray is strictly < i. When we reach a total of exactly i, the current subarray ends and a new subarray (initially having sum 0) begins. If adding the current element takes us above the target of i, or if we run out of elements before reaching the target, stop this scan and try the next outer loop iteration (value of i). OTOH if we get to the end, having formed k subarrays in the process, stop and report n-k as the optimal (minimum possible) number of combining moves.

A small speedup would be to only try target i values that evenly divide T.

EDIT: To improve the time complexity from O(nT) to O(n^2), it suffices to only try target i values corresponding to sums of prefixes of the array (since there must be a subarray containing the first element, and this subarray can only have such a sum).

user_479840
Related