1. BinaryGap
2. OddOcurrencesInArray
CyclicRotation
3. FrogJmp
PermMissingElem
TapeEquilibrium
4. PermCheck
FrogRiverOne
MaxCounters
MissingInteger
5. Passing Cars
GenomicRangeQuery
MinAvgTwoSlice https://app.codility.com/demo/results/trainingMBN972-MEB/
CountDiv https://app.codility.com/demo/results/training5S45PD-Q7F/
6. MaxProductOfThree https://app.codility.com/demo/results/trainingRVPY4T-3ER/
Distinct https://app.codility.com/demo/results/trainingY9S69A-EEZ/
Triangle https://app.codility.com/demo/results/training6RX4UF-S6S/
NumberOfDiscIntersections https://app.codility.com/demo/results/trainingWBGV4A-W8R/
7. Brackets
Fish
StoneWall https://app.codility.com/demo/results/training9J38JW-HSJ/
8. Dominator
EquiLeader
9. MaxProfit
MaxSliceSum
MaxDoubleSliceSum
10. CountFactors https://app.codility.com/demo/results/trainingDP59P3-P5J/
MinPerimeterRectangle https://app.codility.com/demo/results/trainingYTPTCP-HJG/
Peaks
Flags https://app.codility.com/demo/results/training62RKJR-6CV/
/**
* Find longest sequence of zeros in binary representation of an integer.
* A _binary gap_ within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N/**
* Find longest sequence of zeros in binary representation of an integer.
*/
class BinaryGapClass {
function binaryGap($n)
{
if ($n==0) { return 0;}
$binary = ($n);
$binaryA = ($binary);
$count = ($binaryA);
$start = 0;
$end = 0;
$max = 0;
$i = 0;
$j = $count-1;
while ($binaryA[$i]==0) {
if ($binaryA[$i]==0) {
($binaryA[$i]);
$i++;
}
}
while ($binaryA[$j]==0) {
if ($binaryA[$j] == 0) {
($binaryA[$j]);
$j--;
}
}
$count = ($binaryA);
$start = 0;
$end = 0;
while ($end < $count) {
if ($binaryA[$end] == 0) {
$end++;
} else {
$end++;
$start = $end;
}
$distance = $end-$start;
$max = ($max, $distance);
}
return $max;
}
}
/**
* array with integers that appear an even number of times, but one. Find that valueFind value that occurs in odd number of elements.
*/
class OddOccurrencesInArrayClass {
function oddOccurrencesInArray($n)
{
$countArray = [];
foreach ($n as $item) {
if (($countArray[$item])) {
$countArray[$item]++;
} else {
$countArray[$item] = 1;
}
}
foreach ($countArray as $key=>$item) {
if ($item%2!==0) {
return $key;
}
}
}
}
/**
* Rotate an array to the right by a given number of steps.
*/
class CyclicRotationClass {
function rotate(&$nums, $k)
{
if (($nums)==0) {return $nums;}
$k = $k%($nums);
for ($i = 0; $i < $k; $i++) {
$lastNumber = ($nums);
($nums, $lastNumber);
}
return $nums;
}
}
/**
* Count minimal number of jumps from position X to Y. Jump has a fixed size of D
* */
class frogJumpClass {
function frogJump($x, $y, $d) {
return (($y-$x)/$d);
}
}
/**
* Find the missing element in a given permutation. */
class PermMissingElemClass {
function missingEl($array) {
$sum1 = ($array);
$array = ($array);
$sum2 = ($array) + ($array)*2 +1;
return $sum2-$sum1;
}
}
/**
Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.
For example: [3, 1, 2, 4, 3]
, consider array A such that:
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
We can split this tape in four places:
P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
Return 1
*/
class tapeEquilibriumClass {
function tapeEquilibrium($array) {
$count = ($array);
if ($count == 2) {
return ($array[0]-$array[1]);
}
$sumLeft = $array[0];
$min = PHP_INT_MAX;
$sumRight = ($array)-$sumLeft;
for ($j=1; $j<$count; $j++){
$diff = ($sumRight - $sumLeft);
$min = ($diff, $min);
$sumLeft += $array[$j];
$sumRight -= $array[$j];
}
return $min;
}
}
/**
* Check whether array A is a permutation. starting in 1
*/
class PermCheckClass {
function permCheck($array) {
$count = ($array);
$arrayFound = [];
foreach ($array as $item) {
if ($item < 1 || $item > $count) {
return 0;
} else {
if (($arrayFound[$item])) {
return 0;
} else {
$arrayFound[$item] = true;
}
}
}
return 1;
}
}
/**
* Find the earliest time when a frog can jump to the other side of a river.
From position 0 to X+1, falling leaves:
[1,3,1,4,2,3,5,4] position
0 1 2 4 5 6 7 8 second
return 6
*/
class FrogRiverOneClass {
public function earliestTime(int $x, $array)
{
$count = 0;
$i = 0;
$countArray = ($array);
if ($array[0]==$x && $x==1) {
return 0;
}
while ($count < $x && $i < $countArray) {
if (!($stored[$array[$i]])) {
$stored[$array[$i]] = true;
$count++;
}
$i++;
}
if ($count==$x) {
return $i-1;
} else {
return -1;
}
}
}
/**
counters(5, [3,4,4,6,1,4,4])
(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
return [3, 2, 2, 4, 2]
*/
class MaxCountersClass2 {
public function counters(int $x, $array)
{
$max = 0;
$repArray = [];
foreach ($array as $item) {
if ($item>$x) {
if (($repArray)>0) {
$max = ($repArray);
}
} else {
if (($repArray[$item-1])) {
if ($max>$repArray[$item-1]) {
$repArray[$item-1] = $max;
$repArray[$item-1]++;
} else {
$repArray[$item-1]++;
}
} else {
$repArray[$item-1] = $max;
$repArray[$item-1]++;
}
}
}
foreach ($repArray as $key => $item) {
if ($item<$max) {
$repArray[$key] = $max;
}
}
$result = [];
for ($i=0; $i<$x; $i++) {
if (($repArray[$i])) {
$result[$i] = $repArray[$i];
} else {
$result[$i] = $max;
}
}
return $result;
}
}
/**
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
*/
class firstMissingPositiveIntegerClass1 {
/**
* @param Integer[] $nums
* @return Integer
*/
function firstMissingPositive($nums) {
if (($nums) === 0) {
return 1;
}
$nums2 = [];
foreach ($nums as $num) {
if (($nums2[$num])){
continue;
}
$nums2[$num] = $num;
}
$nums = $nums2;
$nums[] = PHP_INT_MIN;
($nums );
foreach ($nums as $key => $num) {
if ($num > 1) {
if (($nums[$key-1]) && $nums[$key-1]!==$nums[$key]-1) {
if ( $nums[$key-1] === PHP_INT_MIN) {
return 1;
} elseif ($nums[$key-1]+1 <= 0) {
return 1;
}
return $nums[$key-1]+1;
}
}
}
if ($num+1 <= 0) {
return 1;
}
return $num+1;
}
}
/**
For example, consider array A such that:
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
return 5
*/
class passingCarsClass {
function passingCars($nums) {
/** @var array $west */
$west = [];
$minHeap = new SplMinHeap();
foreach ($nums as $key => $item) {
if ($item==0) {
$east[$key] = $key;
} elseif ($item==1) {
$minHeap->insert($key);
}
}
$passing = 0;
foreach ($east as $key => $item) {
while (!$minHeap->isEmpty()) {
if ($item < $minHeap->top()) {
$passing += $minHeap->();
break;
}
$minHeap->();
}
}
if ($passing>1000000000) {
return -1;
}
return $passing;
}
}
/**
A, C, G and T have impact factors of 1, 2, 3 and 4,
consider string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6
return minimun value for each query
return [2, 4, 1]
*/
class GenomicRangeQueryClass
{
public function genomicRangeQuery (string $s, $p, $q)
{
$impactFactor = [
1 => 'A',
2 => 'C',
3 => 'G',
4 => 'T'
];
$arrayRepetitions = [];
for ($i = 0; $i < ($s); $i++) {
for ($j = 1; $j <= ($impactFactor); $j++) {
$arrayRepetitions[$i][$j] = ($arrayRepetitions[$i - 1][$j])
? $arrayRepetitions[$i - 1][$j]
: 0;
if ($s[$i] == $impactFactor[$j]) {
$arrayRepetitions[$i][$j]++;
}
}
}
$M = ($p);
$minSubsequenceImpactFactors = [];
for ($i = 0; $i < $M; $i++) {
for ($j = 1; $j <= ($impactFactor); $j++) {
// Left and right sequence boundary
$left = ($arrayRepetitions[$p[$i] - 1][$j]) ? $arrayRepetitions[$p[$i] - 1][$j] : 0;
$right = $arrayRepetitions[$q[$i]][$j];
if ($left < $right) {
$minSubsequenceImpactFactors[] = $j;
;
}
}
}
return $minSubsequenceImpactFactors;
}
}
/**
Find the minimal average of any slice containing at least two elements.
*/
class MinAvgTwoSliceClass {
function MinAvgTwoSlice( $A) {
$length = ($A);
$min_average = ($A[0] + $A[1]) / 2.0;
$position = 0;
if ($length==2) return 0;
for ($i=2 ; $i < $length; $i++) {
$temp1 = ($A[$i-1] + $A[$i]) / 2.0;
$temp2 = ($A[$i-2] + $A[$i-1] + $A[$i]) / 3.0;
if ($temp1 < $min_average) {
$position = $i - 1;
$min_average = $temp1;
}
if ($temp2 < $min_average) {
$position = $i - 2;
$min_average = $temp2;
}
}
return $position;
}
}
/**
given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:
*/
class CountDivClass {
function countDiv($A, $B, $K) {
if($A%$K==0) {
$result = (($B-$A)/$K)+1;
} else {
$countDivUnderA = ($A/$K)+1;
$result = ($B/$K-($countDivUnderA))+1;
}
return (int)$result;
}
}
/**
that, given an array A consisting of N integers, returns the number of distinct values in array A.
*/
class DistinctClass
{
public function distinct($array)
{
$uniqueArray = [];
foreach ($array as $item) {
if (!($uniqueArray[$item])) {
$uniqueArray[$item] = true;
}
}
return ($uniqueArray);
}
}
/**
An array A consisting of N integers is given. A triplet (P, Q, R) is _triangular_ if 0 ≤ P < Q < R < N and:
> - A[P] + A[Q] > A[R],
> - A[Q] + A[R] > A[P],
> - A[R] + A[P] > A[Q].
For example, consider array A such that:
A[0] = 10
A[1] = 2
A[2] = 5
A[3] = 1
A[4] = 8
A[5] = 20
Triplet (0, 2, 4) is triangular.
Write a function:
> class Solution { public int solution(int[] A); }
that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
For example, given array A such that:
A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20
the function should return 1, as explained above. Given array A such that:
A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1
the function should return 0.
*/
class TriangleClass
{
function triangle($A)
{
$count = ($A);
if ( $count < 3 )
return 0;
($A, SORT_NUMERIC);
for ( $i = 0; $i < $count-2; ++$i ) {
if ( $A[$i] + $A[$i+1] > $A[$i+2] ) {
return 1;
}
}
return 0;
}
}
/**
find the maximal product of any triplet.
*/
class MaxProductOfThreeClass
{
function MaxProductOfThree($array)
{
($array);
$last = ($array)-1;
$one = $array[$last]*$array[$last-1]*$array[$last-2];
$two = PHP_INT_MIN;
if ($array[0]<0 && $array[1]<0) {
$two = ($array[0])*($array[1])*$array[$last];
}
return ($one, $two);
}
}
/**
We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
*/
class NumberOfDiscIntersectionsClass
{
function numberOfDiscIntersections($array)
{
$lKth = [];
$rJth = [];
$count = 0;
for ($i = 0; $i<($array); $i++) {
$lKth[$i] = $i - $array[$i];
$rJth[$i] = $i + $array[$i];
}
($lKth);
($rJth);
for ($i=0; $i<($array)-1; $i++){
for ($j = $i+1; $j < ($array); $j++) {
if ($rJth[$i]>=$lKth[$j]) {
$count++;
if ($count>10000000) {
return -1;
}
}
}
}
return $count;
}
}
/**
Determine whether a given string of parentheses (multiple types) is properly nested.
*/
class BraketsClass {
function solution($s) {
$inArray = ['(', '{', '['];
$outArray = [')', '}', ']'];
$correspondantArray = [ ')' => '(', '}' => '{', ']' => '['];
$stack = new \SplStack();
$string = ($s);
if ($s == "") {
return 1;
}
foreach ($string as $item) {
if (\($item, $inArray, true)) {
$stack->push($item);
} elseif (\($item, $outArray, true)) {
if (($correspondantArray[$item]) && !$stack->isEmpty() && $correspondantArray[$item] === $stack->top()) {
$stack->pop();
} else {
return 0;
}
} else {
return 0;
}
}
return (int) $stack->isEmpty();
}
}
/**
N voracious fish are moving along a river. Calculate how many fish are alive.
Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:
- 0 represents a fish flowing upstream,
- 1 represents a fish flowing downstream.
If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:
> - If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
> - If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.
We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.
For example, consider arrays A and B such that:
A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0
Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.
return 2,
*/
class FishClass
{
function fish($A, $B)
{
$sizeOfA = ($A);
$deadFish = 0;
$downstreamFishArray = ();
for($i=0; $i<$sizeOfA; $i++){
if($B[$i] == 1){
($downstreamFishArray, $A[$i]);
}elseif(($downstreamFishArray[0])){
$exitGate = false;
while(($downstreamFishArray[0]) && !$exitGate){
$deadFish++;
if($A[$i] > ($downstreamFishArray)){
($downstreamFishArray);
}else{
$exitGate = true;
}
}
}
}
return $sizeOfA - $deadFish;
}
}
/**
given array H containing N = 9 integers:
H[0] = 8 H[1] = 8 H[2] = 5
H[3] = 7 H[4] = 9 H[5] = 8
H[6] = 7 H[7] = 4 H[8] = 8
the function should return 7. The figure shows one possible arrangement of seven blocks.
*/
class StoneWallClass
{
public function stoneWall ( $array)
{
$count = 0;
// Stack of horizontal edges, such that their heights form an increasing sequence
$stack = [];
foreach ($array as $height) {
// While there are stone blocks in stack, and horizontal edge is higher than current height
while (($stack) && $stack[($stack) - 1] > $height) {
// Horizontal edges which are higher than the current height are removed
($stack);
}
// If stack is empty, or last stone block height is different than current height
if (($stack) == 0 || $stack[($stack) - 1] != $height) {
// Current horizontal edge is pushed to the stack
($stack, $height);
// Stone blocks counter is increased
$count++;
}
}
return $count;
}
}
/**
Find an index of an array such that its value occurs at more than half of indices in the array.
For example, given array A such that
A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3
the function may return 0, 2, 4, 6 or 7, as explained above.
*/
class DominatorClass
{
function dominator($H)
{
$counterArray = [];
foreach ($H as $item) {
if (($counterArray[$item])) {
$counterArray[$item]++;
} else {
$counterArray[$item] = 1;
}
}
$max = ($counterArray);
if ($max>($H)/2) {
$key = ($max, $counterArray);
$result = ($key, $H);
if ($result===false) {
return -1;
} else {
return $result;
}
} else {
return -1;
}
}
}
/**
Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same.
The leader of this array is the value that occurs in more than half of the elements of A.
given array A such that:
A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2
we can find two equi leaders:
0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.
return 2
*/
class EquiLeaderClass2
{
public function equiLeader ( $array)
{
$fromLeft = [];
$fromRight = [];
$count = ($array);
$fromLeftOcurrences = [];
$max = P
HP_INT_MIN;
$leader = $array[0];
for ($i=0; $i<$count; $i++) {
if (($fromLeftOcurrences[$array[$i]])) {
$fromLeftOcurrences[$array[$i]]++;
} else {
$fromLeftOcurrences[$array[$i]] = 1;
}
if ($fromLeftOcurrences[$array[$i]]>$max) {
$max = $fromLeftOcurrences[$array[$i]];
$leader = $array[$i];
} elseif ($fromLeftOcurrences[$array[$i]] == $max && $i!==0) {
$leader = null;
}
if ($max>($i+1)/2) {
$fromLeft[$i] = $leader;
} else {
$fromLeft[$i] = null;
}
}
$fromRigthOcurrences = [];
$max = PHP_INT_MIN;
$leader = $array[$count-1];
$j = 0;
for ($i=$count-1; $i>=0; $i--) {
if (($fromRigthOcurrences[$array[$i]])) {
$fromRigthOcurrences[$array[$i]]++;
} else {
$fromRigthOcurrences[$array[$i]] = 1;
}
if ($fromRigthOcurrences[$array[$i]]>$max) {
$max = $fromRigthOcurrences[$array[$i]];
$leader = $array[$i];
} elseif ($fromRigthOcurrences[$array[$i]] == $max && $i!==0) {
$leader = null;
}
if ($max>($j+1)/2) {
$fromRight[$i] = $leader;
} else {
$fromRight[$i] = null;
}
$j++;
}
$number = 0;
($fromLeft, $fromRight);
for ($i=0; $i<$count-1; $i++) {
if ($fromLeft[$i]==$fromRight[$i+1] && $fromLeft[$i]!==null) {
$number++;
}
}
return $number;
}
}
/**
Given a log of stock prices compute the maximum possible earning in one transaction
*/
class maxProfitClass {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$minValue = ($prices);
$maxProfit = 0;
$count = ($prices);
for ($i = 0; $i < $count; $i++) {
if ($prices[$i] < $minValue) {
$minValue = $prices[$i];
continue;
}
if ($prices[$i] - $minValue > $maxProfit) {
$maxProfit = $prices[$i] - $minValue;
}
}
return $maxProfit;
}
}
/**
Find a maximum sum of a compact subsequence of array elements.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:
(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
*/
class MaxSliceSumClass
{
function ($n)
{
$max = PHP_INT_MIN;
$partialSum = 0;
foreach ($n as $key => $item) {
$partialSum += $item;
if ($partialSum>=0) {
if ($max<=$partialSum) {
$max = $partialSum;
}
} else {
if ($max<=$partialSum) {
$max = $partialSum;
}
$partialSum = 0;
}
}
return $max;
}
}
/**
Find the maximal sum of any double slice.
A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a _double slice_.
The _sum_ of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1].
For example, array A such that:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
contains the following example double slices:
double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
double slice (0, 3, 7), sum is 2 + 6 + 4 + 5 − 1 = 16,
double slice (3, 4, 5), sum is 0.
return 17
*/
class MaxDoubleSliceSumClass
{
function maxDoubleSlice($A)
{
$N = ($A);
// Calculating left and right slice sum on every index, marginal integers are not counted
for ($i = 1; $i < $N - 1; $i++) {
$previousIndexLeftMaxSliceSums =
($leftMaxSliceSums[$i - 1]) ? $leftMaxSliceSums[$i - 1] : 0;
// Sum cannot be negative because we can always pick triplet with no indexes in between
$leftMaxSliceSums[$i] = (0, $previousIndexLeftMaxSliceSums + $A[$i]);
}
for ($i = $N - 2; $i > 0; $i--) {
$nextIndexRightMaxSliceSums = ($rightMaxSliceSums[$i + 1]) ? $rightMaxSliceSums[$i + 1] : 0;
$rightMaxSliceSums[$i] = (0, $nextIndexRightMaxSliceSums + $A[$i]);
}
($leftMaxSliceSums, $rightMaxSliceSums);
// Maximum double slice sum
$maxDoubleSliceSum = 0;
// Maximum sum slices before and after the index are summed and maximum double slice sum is searched
for ($i = 1; $i < $N - 1; $i++) {
$leftMaxSliceSum = ($leftMaxSliceSums[$i - 1]) ? $leftMaxSliceSums[$i - 1] : 0;
$rightMaxSliceSum = ($rightMaxSliceSums[$i + 1]) ? $rightMaxSliceSums[$i + 1] : 0;
$doubleSliceSum = $leftMaxSliceSum + $rightMaxSliceSum;
if ($doubleSliceSum > $maxDoubleSliceSum) {
$maxDoubleSliceSum = $doubleSliceSum;
}
}
return $maxDoubleSliceSum;
}
}
/**
Find the maximal sum of any double slice.
6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).
given a positive integer N, returns the number of its factors.
*/
class CountFactorsClass
{
function solution($n) {
if ($n==1) {
return 1;
}
$factors = 0;
$i=1;
while ($i*$i<$n) {
if ($n%$i==0) {
$factors += 2;
}
$i++;
}
if ($i * $i == $n){
$factors += 1;
}
return $factors;
}
}
/**
Find the minimal perimeter of any rectangle whose area equals N.
The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).
N = 30, rectangles of area 30 are:
(1, 30), with a perimeter of 62,
(2, 15), with a perimeter of 34,
(3, 10), with a perimeter of 26,
(5, 6), with a perimeter of 22.
return 22,
*/
class MinPerimRectClass
{
function minPerimRect($n)
{
if ($n==1) {
return 4;
}
$min = PHP_INT_MAX;
$i=1;
while ($i*$i<$n) {
if ($n%$i==0) {
$sideA = $i;
$sideB = $n/$i;
$min = ($min, $sideA*2+$sideB*2);
}
$i++;
}
if ($i * $i == $n){
$min = ($min, $i*2+$i*2);
}
return $min;
}
}
/**
Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < A[P] > A[P + 1].
return The maximum number of blocks that array A can be divided into
*/
class PeaksClass
{
function solution($n)
{
$peaks = [];
foreach ($n as $key => $item) {
if ((($n[$key-1]) && $n[$key-1]<$item) && ($n[$key+1]) && ($n[$key+1]<$item)) {
$peaks[] = $key;
}
}
$countN = ($n);
$countPeaks = ($peaks);
if ($countPeaks==0) {
return 0;
}
while ($countPeaks*($countPeaks)>$countPeaks) {
$countPeaks--;
}
// var_dump($countN, $countPeaks);die;
if ($countN%$countPeaks==0) {
//ver que los peaks están dentro de los intervalos correctos
$countPeaks++;
while ($countPeaks>=0) {
$countPeaks--;
$numberOfElementsPerBlock = $countN/$countPeaks;
if ($countN%$countPeaks!==0) {
continue;
}
$j = 0;
for ($i=0;$i<=4;$i+=$numberOfElementsPerBlock) {
if ($i==0) {
continue;
}
if ($peaks[$j]>$i) {
return 0;
}
}
return $countPeaks;
}
} else {
if ($countPeaks>0) {
return 1;
}
}
return $countPeaks;
}
}
/**
The goal is to set the maximum number of flags on the peaks, according to certain rules.
flags should be greater than or equal to K. The distance between indices P and Q is the absolute value |P − Q|.
*/
class FlagsClass
{
public function solution($array)
{
if (($array) == 0 || ($array) == 1 || ($array) == 2) {
return 0;
}
$count = ($array);
$peaks = [];
$first = -1;
$last = -1;
$startTime = (true);
foreach ($array as $key => $value) {
if ($key > 0 && $key < $count-1 && $value > $array[$key - 1] && $value > $array[$key + 1]) {
if ($peaks == []) {
$first = $key;
}
$peaks[] = $key;
$last = $key;
}
}
$distanceExtremePeaks = $last-$first;
$flags = 1;
$countPeaks = ($peaks);
if ($countPeaks == 0) {
return 0;
}
if ($countPeaks == 1) {
return 1;
}
$i = $first;
$keyPeaks = 1;
while ($countPeaks*($countPeaks-1)>$distanceExtremePeaks) {
$countPeaks--;
}
while ($countPeaks >= 1) {
while ($i <= $last) {
$i += $countPeaks;
while (($peaks[$keyPeaks]) && $i > $peaks[$keyPeaks]) {
$keyPeaks++;
}
if (!($peaks[$keyPeaks])) {
$countPeaks--;
$i = $first;
$keyPeaks = 1;
$flags = 1;
continue;
}
$i = $peaks[$keyPeaks];
$flags++;
if ($flags >= $countPeaks) {
$endTime = (true);
$diff = ($endTime - $startTime);
return $flags;
}
}
}
}
}
