Skip to content

Instantly share code, notes, and snippets.

@pdolinaj
Last active August 29, 2015 14:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pdolinaj/f886b336d6db9659907f to your computer and use it in GitHub Desktop.
Save pdolinaj/f886b336d6db9659907f to your computer and use it in GitHub Desktop.
Return number of arithmetic slice in a given set - Solution to a problem on CODILITY
//Return number of arithmetic slices in a given set
public function numberOfArithmeticSlicesFromSet(array $A)
{
$numbersCount = count($A);
//mininum length of arithmetic slice is 3
if($numbersCount < 3)
return 0;
$startOfSlice = 0;
$numberOfSlices = 0;
while($startOfSlice < $numbersCount-2) {
$endOfSlice = $startOfSlice+1;
$arithmeticDifference = $A[$endOfSlice] - $A[$startOfSlice];
//continue in set until condition fails
while($endOfSlice < $numbersCount-1 && $A[$endOfSlice+1] - $A[$endOfSlice] == $arithmeticDifference) {
$endOfSlice++;
}
//this is the length of the found arightmetic slice
$lengthOfSlice = $endOfSlice - $startOfSlice + 1;
//at least 3 number must be in any valid slice
if($lengthOfSlice >= 3){
$numberOfSlices += (($lengthOfSlice-2)*($lengthOfSlice-1)/2);
}
$startOfSlice = $endOfSlice;
}
//sanity check
return ($numberOfSlices > 1000000000) ? -1 : $numberOfSlices;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment