Skip to content

Instantly share code, notes, and snippets.

@TheSETJ
Last active August 31, 2022 19:29
Show Gist options
  • Save TheSETJ/65e0906f46796eb4bb5bcf992722ee5a to your computer and use it in GitHub Desktop.
Save TheSETJ/65e0906f46796eb4bb5bcf992722ee5a to your computer and use it in GitHub Desktop.
A function to calculate minimum steps required to make sure there are equal amount of coin in each bag
<?php
$c = [0,6,0];
$n = count($c);
$k = array_sum($c) / $n;
/*
* Consider having "n" bags in which there are ci coins (i=1 to n)
* as such that total count of coins are dividable by n and equal to "k".
*
* If we define a step as picking one coin from one bag and dropping it
* in one of the adjacent bags (either left-side or right-side), how can we
* calculate minimum steps required to make sure there are "k" coins
* in each and every bag?
*
* Minumum Steps = |c1-k| + |c1+c2-2k| + |c1+c2+c3-3k| + ... + |c1+c2+...+cn-nk|
*
* c = Bags
* n = Bags Count
* k = Expected Coin Per Bag
*
* Sum of ci (for i=1 to n)=nk
*/
function calculateOptimumSteps(array $bags, int $bagsCount, int $expectedCoinPerBag)
{
$cumulativeCoinCount = 0;
$optimumStepsCount = 0;
for ($index = 0; $index < $bagsCount; $index++) {
$cumulativeCoinCount += $bags[$index];
$optimumStepsCount += abs($cumulativeCoinCount - ($index + 1) * $expectedCoinPerBag);
}
return $optimumStepsCount;
}
print(json_encode($c) . " will be processed in " . calculateOptimumSteps($c, $n, $k) . " steps.");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment