Sunday, June 3, 2018

we have another interesting array to discuss
we want to split a positive integer array such that the left and right are as nearly balanced as possible.
we discussed a two pass solution where we find the sums from the left and the right ends and then compare these at each candidate position
we also discussed evaluating each candidate position by adjusting the left and the right if we know the entire sum


int GetPartition(List<int> A) 
    int n = A.Count; 
    int sum = A.Sum();  // O(N)
  
    Int min = sum; 
    int index = 0; 
    int left = 0;
    int right = sum;
    for (int i = 0; i < n - 1; i++) {
        left = left + A[i];
        right = right – A[i];
        if (Math.Abs(left –right) < min) { 
           min = Math.Abs(left - right) ; 
           if (right < left) { 
               index = i + 1; 
            } else { 
               index = i; 
            } 
        } 
    } 
    return index; 


This is still not one-pass because the initialization of the sum variable is a linear operation but this is definitely simpler than the earlier prefix and suffix information  The key takeaway here is that we need sum from both sides to determine the partition. 
When we have the sum already for the elements encountered so far, we can look back to determine the partition. Each additional element encountered as the array grows requires a check for the partition in the already known array.
This makes one-pass difficult. For one-pass we may need additional stats such as the minimum average encountered so far
for 5 3 1 6
the averages would be 5, 4, 3 4 and we could take the point of split as zero based index 2. This assumes there is only one local minima. In some cases we may have more than one minima. In such cases we may consider the last occurrence of the most common average or some other heuristic which jives with the goal that the badness of the array as the square of the difference between the array element and the acceptable average is reduced. The easiest way to test this is to have all permutations of three positive distinct integers

No comments:

Post a Comment