4 kuy - Twice Linear

1. Le challenge

1.1 Instructions

Consider a sequence u where u is defined as follows:

* The number u(0) = 1 is the first one in u.
* For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.
* There are no other numbers in u.

Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

Task:
Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u (so, there are no duplicates).

Example:
dbl_linear(10) should return 22

Note:
Focus attention on efficiency

1.2 Your code

<?php
function dblLinear($n) {
    // your code
}

1.3 Sample test

<?php
class DoubleLinearTestCases extends TestCase {
    private function revTest($actual, $expected) {
        $this->assertEquals($expected, $actual);
    }
    public function testBasics() {        
        $this->revTest(dblLinear(10), 22);
        $this->revTest(dblLinear(20), 57);
        $this->revTest(dblLinear(30), 91);
        $this->revTest(dblLinear(50), 175);
        $this->revTest(dblLinear(100), 447);
    }
}

2. Proposition de solution

<?php
function dblLinear($n)
{
    $i = 0;
    $yArray = [];
    $zArray = [];
    $nextValue = 1;

    while (true) {
        if ($n === $i) {
            return $nextValue;
        }        
        
        $y = 2 * $nextValue + 1;
        $yArray[] = $y;
        $z = 3 * $nextValue + 1;
        $zArray[] = $z;
        
        $nextValue = min($yArray[0], $zArray[0]);
        
        if ($nextValue === $yArray[0]) {
            array_shift($yArray);
        }
        
        if ($nextValue === $zArray[0]) {
            array_shift($zArray);
        }
        
        ++$i;
    }
}