EQUILIBRIUM FUNCTION

[crashmaster]

Hi there,

 

i have a task, to write function in php.

Who can help me?

There is a task:

 

Equilibrium (EQ) Index  of a sequence (array) is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

For example, in array A:

 

Array:

A[0] = -7

A[1] = 1

A[2] = 5

A[3] = 2

A[4] = -4

A[5] = 3

A[6] = 0

 

3 is an EQ index, beacuse:  A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

6 is also EQ index, coz: A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0

(sum of zero elements is zero) 7 is not an EQ index, because it is not a valid index of array A

 

Assume the sum of zero elements is equal zero. Write a function.

 

[Mchl]

Sounds like homework to me and we do not do your homework for you here.

 

We will help you however if you show that you're working on the solution yourself. So... what have you tried so far?

[Daniel0]

Sounds like homework to me and we do not do your homework for you here.

 

Pretty sure most schools have vacation now.

[Mchl]

How about summer programming courses?

[Alex]

Regardless of if it's a homework question or not (it sure sounds like one to me..) you should try it on your own, or show us what you've tried so we can help out. Specifically you might want to look into these functions: array_sum and array_slice. Once you've shown some effort I'll post my solution 

[crashmaster]

What do you think about this fn ??

$a[0] = -7;
$a[1] = 5;
$a[2] = 1;
$a[3] = 2;
$a[4] = -4;
$a[5] = 3;
$a[6] = 0;


//Dumping input array
echo '<pre>';
print_r($a);
echo '</pre><hr>';

function equi($a,$index=0)
{
  //<______________ARRAY OF NUMBERS_______________>///
  //<-------R--<====  |EQ index| =====>----R------>///
  //<---|lower_ind|---|EQ index|---|higher_ind|--->///

  $lower_indexes = $higher_indexes = intval(0); //SUM OF INDEXES

  $lower_values = $higher_values = array(); //ELEMENTS OF (HIGHER|LOWER) INDEXES SUM

  foreach ($a as $k=>$v)
  {
    //Counting SUM of |lower_ind|
    if ($k < $index)
    {
        $lower_indexes = $lower_indexes + $v;
        $lower_values[] = 'A['.$k.']';
    }

    //Counting SUM of |higher_ind|
    if ($k > $index)
    {
        $higher_indexes  = $higher_indexes + $v;
        $higher_values[] = 'A['.$k.']';
    }

  }


  echo 'SEARCHING INDEX IS: <strong>'.$index.'</strong><br>';
  echo 'SUM OF <strong>LOWER</strong> INDEXES ('.implode(' + ',$lower_values).') IS: '.$lower_indexes.'<br>';
  echo 'SUM OF <strong>HIGHER</strong> INDEXES ('.implode(' + ',$higher_values).') IS: '.$higher_indexes.'<br>';


  //Searching EQ index
  if ($lower_indexes == $higher_indexes)
  {
    echo '<font color="red"><strong><u>EQUILIBRIUM INDEX IS: '.$index.'</u></strong></font>.';
  } else {
    echo 'Not found.';
  }

  //How many times are allowed to run program in cycle (till end of array indexes)
  $steps = (count($a) - 1);

  if ($index < $steps)
  {

    echo ' Searching again with new index <b>'.($index + 1).'</b>...<br>-----------------------------------------<br>';
    $index++;
    equi($a,$index);

  } else {
    echo '<hr>Program STOP...';
  }


}

//Run
equi($a);

 

[Alex]

Well, that's one way to do it, but if you utilize some of PHP's built in functions I think you can make things easier on yourself. Here's my solution to the given problem:

 

function getEquilibriums($arr) {
$equilibriums = array();
for($i = 0, $n = sizeof($arr);$i < $n;++$i) {
	if(array_sum(array_slice($arr, 0, $i)) == array_sum(array_slice($arr, $i + 1))) {
		$equilibriums[] = $i;
	}
}
return $equilibriums;
}

$arr = array(-7, 1, 5, 2, -4, 3, 0);
print_r(getEquilibriums($arr));

 

It's pretty simple really. Essentially it does the same thing as yours, it just does it in a shorter procedure. It simply loops through each position in the array with the for loop and checks if the sum of the lower part equals the sum of the upper part utilizing array_sum and array_slice.

[crashmaster]

Thanks, you helped me ))) Yes, your function is pretty simple )) Thanks a lot))

[barabasz]

AlexWD's solution...

 

function getEquilibriums($arr) {
$equilibriums = array();
for($i = 0, $n = sizeof($arr);$i < $n;++$i) {
	if(array_sum(array_slice($arr, 0, $i)) == array_sum(array_slice($arr, $i + 1))) {
		$equilibriums[] = $i;
	}
}
return $equilibriums;
}

 

...is OK, but array_sum and array_slice functions are slow on very large long sequences. Moreover it's counting same values several times. It's better to use foreach function like in this simple example:

 

function getEquilibriums1($arr) {
    $right = array_sum($arr);
    $left = 0;
    $equilibriums = array();
    foreach($arr as $key => $value){
        $right -= $value;
        if(($left) == ($right)) $equilibriums[] = $key;
        $left += $value;
    }
    return $equilibriums;
}

 

but the best and IMHO the fastest way is to use for statement:

 

function getEquilibriums2($arr) {
    $count = count($arr);
    $left = 0;
    $right = array_sum($arr);
    $equilibriums = array();
    for ($i = 0; $i < $count; $i++) {
        $right -= $arr[$i]; 
        if ($left == $right) $equilibriums[] = $i;
        $left += $arr[$i];
    }
    return $equilibriums;    
}