Last active
August 31, 2022 19:29
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?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