Geek asks and answers

Search for a balance point in an array

This question is related to the large YouTube channel, which gives problems that may be asked in an interview.

This is mainly due to the search for the balance point in the array. Here is an example to better explain this; {1,2,9,4, -1}. Here, since the sum (1 + 2) = sum (4 + (- 1)) makes 9 a balance point . Without checking the answer, I decided to implement the algorithm before I wanted to ask if a more efficient approach could be made;

  • Sum all elements of the O (n) array
  • Get half the amount of O (1)
  • Start scanning the array on the left and stop when sumleft is more than half the total. <B> o (n)
  • Do the same for the right to get sum right. O (n) .
  • If sumleft is equal to sumright return arr [size / 2] else return -1

I ask because this solution appeared in my head without any effort, providing O (n) time. Is this solution possible if it is true, or if any alternative methods are not true?

+5
source share
5 answers

( : 1 -1 1 0 1 -1 1), ( sumleft sumright O (1) ), ( , ) , , sumleft = sumright, O (n).

A

[A[0], A[0]+A[1], A[0]+A[1]+A[2], …, A[0]+A[1]+A[2]+…+A[n-1]]

:

A=[5,2,3,1,4,6]
partial sum = [5,7,10,11,15,21]

sumleft[i]=partial_sum[i-1] sumright[i]=partial_sum[n-1]-partial_sum[i]

:

, O (1) O (n) , partial_sum.

+5

, (leftLoc) (rightLoc). sumLeft sumRight.

leftLoc  = 0;
rightLoc = (n - 1);
sumRight = array[rightLoc];
sumLeft  = array[leftLoc];

while(leftLoc < rightLoc){
    if(sumRight > sumLeft){
        leftLoc++;
        sumLeft += array[leftLoc];
    }else{
        rightLoc--;
        sumRight += array[rightLoc];
    } 
}

if( (sumRight + array[rightLoc - 1]) == sumLeft ){
    return rightLoc--;
}else if( (sumLeft + array[leftLoc + 1]) == sumRight){
    return leftLoc++;
}else{
    // return floating point number location in the middle of the 2 locations
}

, O (n)

, ( ).

. , , O (n).

+1

. Python:

def centroid(input_list):
    idx_val_sum = 0.0
    val_sum = 0.0
    for idx,val in enumerate(input_list):
        idx_val_sum += idx*val
        val_sum += val
    return idx_val_sum/float(val_sum)

O (n), , :

def integer_centroid(input_list):
    idx_val_sum = 0.0
    val_sum = 0.0
    for idx,val in enumerate(input_list):
        idx_val_sum += idx*val
        val_sum += val
    out = idx_val_sum/float(val_sum)
    if out%1.0==0.0:
        return out
    else:
        raise ValueError("Input list has non-integer centorid.")

, 14 2012 , . "" idx_val_sum, , .

Edit:

, . , , ++. () ++, .

: f1 f2, x1 x2, , (f1 * x1 + F2 * 2)/(F1 + F2). x f, .

// untested code:

float centroid(float * vec, int vec_length){

  float idx_val_sum = 0.0;
  float val_sum = 0.0;

  for (idx = 0; idx < vec_length; idx++){

    // keep a running sum of the product of the index and the value
    idx_val_sum += float(idx)*vec[idx];

    // similarly, keep a running sum of the index
    val_sum += vec[idx];

  }
  // return the quotient of the product-sum and the index sum:
  return idx_val_sum/val_sum;
}
+1

, . O (n). , , upper == lower. , O (n).

int BalancePoint(int a[], int begin, int end) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1
{
    if(!a) return -1;
    else if(begin == end) return begin;

        long long upper = 0;
        long long lower = 0;

    for(int i = begin; i <= end; ++i)
    {
        upper += *(a+i);
    }

    for(int j = begin; j <= end; ++j)
    {
        upper -= *(a+j);
        if(upper == lower) return j;
        lower += *(a+j);
    }
    return -1;
}

Using STL

int BalancePointSTL( const vector<int> &A ) // find index of an array (balance point) such that sum of all elements before the index = sum of all elements after it; else return -1
{
    if(A.empty()) return -1;

        long long upper = 0;
        long long lower = 0;

    for(unsigned int i = 0; i <= A.size(); ++i)
    {
        upper += A[i];
    }

    for(unsigned int j = 0; j < A.size(); ++j)
    {
        upper -= A[j];
        if(upper == lower) return j;
        lower += A[j];
    }
    return -1;
    }

The following will have better worst case performance, but a couple more comparisons if-else

int BalancePoint2(int a[], int begin, int end) // Better worst case senario by factor of 2
{
    if(!a) return -1;
    else if(begin == end) return begin;

        long long upper = 0;
        long long lower = 0;

        int mid = (end-begin)/2;

        for(int i = begin; i < mid; ++i)
        {
            lower += *(a+i);
        }
        for(int i = mid+1; i <= end; ++i)
        {
            upper += *(a+i);
        } 

        if(upper == lower) return mid;
        else if(lower < upper)
        {
            lower += *(a+mid);
            for(int i= mid + 1 ; i <= end ; ++i)
            {
                upper -= *(a + i);
                if(upper == lower) return i;
                lower += *(a + i);
            }
        }
        else {
            upper += *(a + mid);
            for(int i = mid - 1; i >=begin; --i)
            {
                lower -= *(a + i);
                if(upper == lower) return i;
                upper += *(a + i);
            }
        }
        return -1;
}
0
source

I believe you are looking for the Center of Mass , here is a solution written in Go:

func centerOfGravity(a []int) float64 {
  tot := 0.0
  mass := 0.0
  for i := range a {
    tot += float64(i) * float64(a[i])
    mass += float64(a[i])
  }
  return tot / mass
}

This gives you the index of the center of mass in the array, assuming an array based on 0. It can return a non-integer result, since the center of mass can be anywhere in the range of the array.

-1
source

More articles:


All Articles