public function gcd(int $a, int $b)
    {
        if ($a == 0) {
            return $b;
        }
        return $this->gcd($b % $a, $a);
    }

    public function lcm($a, $b)
    {
        return abs($a * $b) / $this->gcd($a, $b);
    }

    public function change()
    {
        $coins = [20, 10, 5, 2];

        $change = 158;

        $remaining = $change;

        foreach($coins as $coin) {

            $current = floor($remaining / $coin);

            if ( $current > 0 ) {
                $return[$coin] = $current;
                $remaining -= $current * $coin;
            }

            if ( $remaining == 0 )
                break;

        }

        if ( $remaining > 0 )
            echo 'NO' . PHP_EOL;
        else
            var_dump($return);



   //     die;
        $coins = [25, 10, 5, 1];
        $x = [];

        $change = 158;
        //

       arsort($coins);
        //sort($coins);

        // return $this->changeRecursive($change, )
        $remains = $change;

//        foreach ($coins as $i => $val){
//            $x[$i] = (int)($remains/$val);
//            $remains %= $val;
//        }

        for($i = 0; $i < count($coins); $i++){
            $x[$i] = (int)($remains/$coins[$i]);
            $remains %= $coins[$i];
        }
        if($remains > 0){
            var_dump("NO"); die;
        }
        var_dump($x);
        //todo Finish this task
    }

public function circular() {
        //sieve
    $primes = [];
    for($i = 2; $i < $N; $i++){
        $primes[$i] = true;
    }
    $N = 100;
    for($i = 2; $i <= $N; $i++){
        $primes[$i] = false;
        for($j = $i*$i; $j <= $N; $j=$j+$i){

        }

        //update i
    }
}
    public function circular2()
    {
        $primes = [
            2,
            3,
            5,
            7,
            11,
            13,
            17,
            37,
            79,
            113,
            197,
            199,
            337,
            1193,
            3779,
            11939,
            19937,
            193939,
            199933,
        ];
        $repunits = [2, 19, 23, 317];
        // 22:56:30
        // 23:02:45

        $N = 100;

        $primes['2'] = true;

        for ( $i = 3; $i <= $N; $i += 2 ) {

            $prime = true;

            for ( $j = 2; $j < $i; $j++ ) {

                if ( $i % $j == 0 ) {
                    $prime = false;
                    break;
                }

            }

            if ( $prime ) {
                $primes['' . $i] = true;
            }

        }

        $circulars = [];

        foreach ($primes as $key => $value) {

            $prime = $key . '';

            $circular = true;

            for ( $i = 0; $i < strlen($prime) - 1 ; $i++ ) {

                $prime = $this->rotate($prime);

                if ( ! isset($primes[$prime]) ) {
                    $circular = false;
                    break;
                }

            }

            if ( $circular )
                $circulars[] = intval($key);

        }

        var_dump($circulars);


    }
    function rotate($str) {

        return substr($str, 1) . $str[0];

    }

    public function toString($int)
    {
       // $str = (string)$int;
//        var_dump($str);
//        //die;
//        $len = strlen($str);
//        $result = "";
//        $backwards = "";
//        for ($i = $len - 1; $i >= 0; $i--) {
//            $backwards .= $str[$i];
//            if (($len - $i) % 3 == 0) {
//                $backwards .= ",";
//            }
//        }

        $separator = '.';
        $backwards = [];

        $i = 0;
        $j = 0;
        while ($int > 0) {
            $backwards[$j] = $int % 10;
            $i++;
            $j++;
            if ($i % 3 == 0) {
                $backwards[$j] = $separator;
                $j++;
            }
            $int = (int)($int / 10);
        }

        //  var_dump($backwards);
        //   die;
        $j = $backwards[count($backwards) - 1] == $separator ? count($backwards) - 2 : count($backwards) - 1;
        $result = "";
        for (; $j >= 0; $j--) {
            $result .= $backwards[$j];
        }

        var_dump($result);
    }

    public function difftime(){
        //1532905320 29 juli 23:02
        $timestamp = 1532905320;
        $now = (new DateTime())->getTimestamp();
        $now = 1533760080;

        $remaining = $now - $timestamp;

        $days = floor($remaining/(60*60*24));
        $remaining -= $days*60*60*24;

        $hours = floor($remaining/(60*60));
        $remaining -= $hours*60*60;

        $mins = floor($remaining/60);
        $remaining -= $mins*60;

        $secs = $remaining;

        $str = "";
        $arr = [ "day" => $days, "hour" => $hours, "minute" => $mins, "second" => $secs];

        foreach ($arr as $unit => $value) {
            if($value > 0){
                $str .= "$value $unit";
                if($value > 1){
                    $str .= "s";
                }
                $str .= ", ";
            }
        }


        $str = rtrim($str, ", ");
        $str = "9 hours";
        $str .= " ago.";
        $index = strrpos($str, ", ");
        if($index !== false){
            $str = substr_replace($str, " and ", $index, strlen(", "));

        }

        var_dump($str); die;

        $str = "";
        $commaIndex = 0;

        if($days > 0){
            $str .= "$days day";
            if($days > 1){
                $str .= "s";
            }
            $str .= ", ";
        }


        echo "$days days, $hours hours, $mins minutes, $secs seconds";

    }

    public function razlomak()
    {
        $test = "A/B+C/D";
        $test = "12/18+6/24";

        $fractions = explode('+', $test);

        $first = explode("/", $fractions[0]);
        $second = explode("/", $fractions[1]);

        $a = $first[0];
        $b = $first[1];
        $c = $second[0];
        $d = $second[1];
        var_dump($a, $b, $c, $d);
        $lcm = $this->lcm($b, $d);
        echo "lcm : $lcm ";
        $mulA = $lcm / $b;

        $mulC = $lcm / $d;

        $upper = ($a * $mulA) + ($c * $mulC);
        echo "  upper: $upper ";
        $gcd = $this->gcd($upper, $lcm);

        echo $upper / $gcd . "/" . $lcm / $gcd;
    }

    public function mnswpr()
    {
        $input = '<<<LOL
X 0 0 0 0 0 0
0 0 0 0 X 0 0
0 X 0 0 X 0 0
0 X 0 0 0 0 0
LOL';

        $board = explode("\n", $input);
        $board = array_slice($board, 1, count($board) - 2);
        $board = array_map(function($item){
            return explode(" ", $item);
        }, $board);
      //  var_dump($board); die;
//        $board = [
//            [1, 0, 0, 0, 0, 0, 1],
//            [0, 0, 0, 0, 1, 0, 0],
//            [0, 1, 0, 0, 1, 0, 0],
//            [0, 1, 0, 0, 0, 0, 0]
//        ];

        $bomb = PHP_INT_MAX;

        $count = [];
        $rows = count($board);
        $columns = count($board[0]);

        //var_dump($rows, $columns);
        //die;
        echo"<pre>";
        for ($r1 = 0; $r1 < $rows; $r1++) {
            for ($c1 = 0; $c1 < $columns; $c1++) {
                //check surrounding for each field
                if ($board[$r1][$c1] != 'X') {

                    $cnt = 0;
                    for ($c2 = $c1 - 1; $c2 <= $c1 + 1; $c2++) {

                        for ($r2 = $r1 - 1; $r2 <= $r1 + 1; $r2++) {
//                            echo "[$r2, $c2]<br>";
                            if ($c2 >= 0 && $r2 >= 0 && !($c2 == $c1 && $r2 == $r1) && $c2 < $columns && $r2 < $rows) {
//                                echo "usao <br>";
//                                echo $board[$r2][$c2];
                                //it's within boundaries
                                if ($board[$r2][$c2] == 'X') {
                                    $cnt++;
                                }
                            }
                        }
                    }
//                    echo $cnt;
//                    die;
                    $count[$r1][$c1] = $cnt;
                    echo $cnt . " ";
                }else {
                     echo "X ";
                }

            }
            echo "<br>";
        }
        echo"</pre>";
        var_dump($count);
    }

    public function decks()
    {
        //0

        //1
        $test = [
            "QC",
            "6D",
            "KD",
            "QS",
            "7S",
            "5C",
            "QH",
            "3H",
            "AD",
            "9C",
            "7H",
            "QD",
            "QH",
            "2S",
            "AH",
            "KS",
            "5D",
            "QC",
            "AS",
            "2D",
            "6C",
            "8C",
            "7D",
            "8H",
            "9S",
            "4D",
            "6H",
            "JC",
            "3S"
            ,
            "4C",
            "3C",
            "7S",
            "KD",
            "4H",
            "5C",
            "7C",
            "AS",
            "3D",
            "7D",
            "2H",
            "8S",
            "2H",
            "8D",
            "9S",
            "3C",
            "5H",
            "KS",
            "8D",
            "9H",
            "TH",
            "2C",
            "JH",
            "6D",
            "KC",
            "TS",
            "6S",
            "TD",
            "4S"
            ,
            "8S",
            "5S",
            "8H",
            "TD",
            "9D",
            "4H",
            "6C",
            "7C",
            "AC",
            "JC",
            "JD",
            "TS",
            "KH",
            "2C",
            "QD",
            "JS",
            "QS",
            "KH",
            "8C",
            "3H",
            "2D",
            "2S",
            "3S",
            "5H",
            "4S",
            "9C",
            "4D",
            "6H",
            "JS"
            ,
            "TH",
            "9H",
            "TC",
            "7H",
            "JH",
            "TC",
            "6S",
            "AD",
            "AC",
            "JD",
            "4C",
            "5D",
            "9D",
            "KC",
            "3D"
        ];

        $test = [
            "9C",
            "KS",
            "AC",
            "AH",
            "8D",
            "4C",
            "KD",
            "JC",
            "7D",
            "9D",
            "2H",
            "7C",
            "3C",
            "7S",
            "5C",
            "6H",
            "TH",
            "7H",
            "QD",
            "9S",
            "KC",
            "2D",
            "4D",
            "9H",
            "4S",
            "8H",
            "3H",
            "3S",
            "5S",
            "6S",
            "TD",
            "5H",
            "8S",
            "4H",
            "6D",
            "JD",
            "TC",
            "AD",
            "JS",
            "2C",
            "5D",
            "JH",
            "QH",
            "3D",
            "KH",
            "8C",
            "TS",
            "6C",
            "QC",
            "QS"
        ];

        //3
        //$test = ["2S", "2C", "2D", "2H", "3S", "3C", "3D", "3H", "4S", "4C", "4D", "4H", "5S", "5C", "5D", "5H", "6S", "6C", "6D", "6H", "7S", "7C", "7D", "7H", "8S", "8C", "8D", "8H", "9S", "9C", "9D", "9H", "TS", "TC", "TD", "TH", "JS", "JC", "JD", "JH", "QS", "QC", "QD", "QH", "KS", "KC", "KD", "KH", "AS", "AC", "AD", "AH", "2S", "2C", "2D", "2H", "3S", "3C", "3D", "3H", "4S", "4C", "4D", "4H", "5S", "5C", "5D", "5H", "6S", "6C", "6D", "6H", "7S", "7C", "7D", "7H", "8S", "8C", "8D", "8H", "9S", "9C", "9D", "9H", "TS", "TC", "TD", "TH", "JS", "JC", "JD", "JH", "QS", "QC", "QD", "QH", "KS", "KC", "KD", "KH", "AS", "AC", "AD", "AH", "2S", "2C", "2D", "2H", "3S", "3C", "3D", "3H", "4S", "4C", "4D", "4H", "5S", "5C", "5D", "5H", "6S", "6C", "6D", "6H", "7S", "7C", "7D", "7H", "8S", "8C", "8D", "8H", "9S", "9C", "9D", "9H", "TS", "TC", "TD", "TH", "JS", "JC", "JD", "JH", "QS", "QC", "QD", "QH", "KS", "KC", "KD", "KH", "AS", "AC", "AD", "AH"];

        //2
        //$test = ["2S", "2C", "2D", "2H", "3S", "3C", "3D", "3H", "4S", "4C", "4D", "4H", "5S", "5C", "5D", "5H", "6S", "6C", "6D", "6H", "7S", "7C", "7D", "7H", "8S", "8C", "8D", "8H", "9S", "9C", "9D", "9H", "TS", "TC", "TD", "TH", "JS", "JC", "JD", "JH", "QS", "QC", "QD", "QH", "KS", "KC", "KD", "KH", "AS", "AC", "AD", "AH", "2S", "2C", "2D", "2H", "3S", "3C", "3D", "3H", "4S", "4C", "4D", "4H", "5S", "5C", "5D", "5H", "6S", "6C", "6D", "6H", "7S", "7C", "7D", "7H", "8S", "8C", "8D", "8H", "9S", "9C", "9D", "9H", "TS", "TC", "TD", "TH", "JS", "JC", "JD", "JH", "QS", "QC", "QD", "QH", "KS", "KC", "KD", "KH", "AS", "AC", "AD", "AH", "2S", "2C", "2D", "2H", "3S", "3C", "3D", "3H", "4S", "4C", "4D", "4H", "5S", "5C", "5D", "5H", "6S", "6C", "6D", "6H", "7S", "7C", "7D", "7H", "8S", "8C", "8D", "8H", "9S", "9C", "9D", "9H", "TS", "TC", "TD", "TH", "JS", "JC", "JD", "JH", "QS", "QC", "QD", "QH", "KS", "KC", "KD", "KH", "AS", "AC", "AD"];


        $ranks = ['2', '3', '4', '5', '6', 7, 8, 9, 'T', 'J', 'Q', 'K', 'A'];
        $suits = ['S', 'C', 'H', 'D'];

        $count = [];

        foreach ($test as $card) {
            if (isset($count[$card])) {
                $count[$card]++;
            } else {
                $count[$card] = 1;
            }
        }

        $min = PHP_INT_MAX;
        foreach ($ranks as $rank) {
            foreach ($suits as $suit) {
                if (!isset($count[$rank . $suit])) {
                    var_dump(0);
                    return;
                } else {
                    if ($count[$rank . $suit] < $min) {
                        $min = $count[$rank . $suit];
                    }
                }
            }
        }
        var_dump($min);
    }

    public function domino()
    {
        $S = "1-1";// => 1
        $S = "1-2,2-2";// => 1
        $S = "3-2,2-1,1-4,4-4,5-4,4-2,2-1";// => 4
        $S = "5-5,5-5,4-4,5-5,5-5,5-5,5-5,5-5,5-5,5-5";// => 7
        $S = "1-1,3-5,5-5,5-4,4-2,1-3";// => 4
        $S = "1-2,2-2,3-3,3-4,4-5,1-1,1-2";// => 3

        if (strlen($S) === 0) {
            var_dump(0);
            return 0;
        }

        $dominos = explode(",", $S);
        $curr = 1;
        $max = 1;
        $length = count($dominos);

        for ($i = 0; $i < $length - 1; $i++) {
            if ($dominos[$i][2] == $dominos[$i + 1][0]) {
                $curr++;
            } else {
                if ($curr > $max) {
                    $max = $curr;
                }
                $curr = 1;
            }
        }
        if ($curr > $max) {
            $max = $curr;
        }

        var_dump($max);
    }

    public function cards()
    {
        $A = [1, 2, 4, 3];
        $A = [3, 2, 1, 4, 5];
        $A = [2];
        $B = [1];
//        for($i = 0; $i < 100000; $i++){
//            $A[$i] = $i;
//            $B[$i] = $i;
//        }
        //  $B = [1,3,2,3];
        // $B = [3,2,1,3,3];

        $temp = [];
        for ($i = 0; $i < count($A); $i++) {
            if ($B[$i] > $A[$i]) {
                $A[$i] = $B[$i];
            }
        }

        echo "A " . implode(", ", $A);
        for ($i = 0; $i < count($A); $i++) {
            $temp[$A[$i]] = true;
        }

        echo "temp " . implode(", ", $temp);
        for ($i = 1; $i < count($A); $i++) {
            if (!isset($temp[$i])) {
                var_dump($i);
            }
        }

        var_dump(count($A) + 1);
    }

    public function test1()
    {
        $a = [5, 5, 5];
        //$a = [5,5,2,5,1,6];
        //$a = [5,5,2,3,5,1,6];
        $x = 5;

        $countX = 0;
        $countO = 0;
        $j = count($a) - 1;//ne treba oba da racunaju ovaj u sredini
        for ($i = 0; $i < count($a) / 2 - 1; $i++) {
            if ($a[$i] == $x) {
                $countX++;
            }
            if ($a[count($a) - 1 - $i] != $x) {
                $countO++;
            }
        }
        if (count($a) % 2) {
            if ($a[$i] == $x) {
                $countX++;
            }
        }
        echo "i: $i" . "<br>";

        echo "X: $countX, notX: $countO";

        while ($countO != $countX) {
            if ($countX > $countO) {
                if ($a[$i] == $x) {
                    $countX--;
                } else {
                    $countO++;
                }
                $i--;
            } else {
                if ($a[$i] == $x) {
                    $countX++;
                } else {
                    $countO--;
                }
                $i++;
            }
        }
        echo "<br> X: $countX, notX: $countO <br>";
        var_dump($i + 1);

    }

    public function giraffe()
    {
//$a = [1,5,4,9,8,7,12,13,14];//dodaj nulu i dodaj izmedju neki broj
        $a = [3, 5, 4, 9, 8, 7, 12, 13, 14];
        $a = [2, 3, 4, 5, 6, 1];
        $a = [2, 4, 1, 6, 5, 9, 7];
        $a = [2, 1, 6, 4, 3, 7];
        asort($a);
        $b = array_keys($a);
//var_dump($b);
        $groups = 0;
        for ($i = 0; $i < count($b); $i++) {
            //var_dump($i);
            $i = $b[$i];
            $groups++;
        }


        var_dump($groups);

    }

    public function sortedArrays()
    {
        $a = [1, 2, 3, 4, 5, 6, 7, 8, 10, 19, 40];
        $b = [-3, -2, -1, 0, 1, 2, 3, 4, 5, 11, 14, 16];
        $c = [];

        $i = 0;
        $j = 0;
        $k = 0;
        $previous = false;
        while ($i < count($a) && $j < count($b)) {

            if ($a[$i] < $b[$j]) {
                $add = $a[$i];
                $i++;
            } elseif ($b[$j] < $a[$i]) {
                $add = $b[$j];
                $j++;
            } else {
                $add = $b[$j];
                $i++;
                $j++;
            }
            if ($previous !== $add) {
                $c[$k] = $add;
                $previous = $c[$k];
                $k++;
            }

        }

        for (; $i < count($a); $i++) {
            $c[$k] = $a[$i];
            $k++;
        }

        for (; $j < count($b); $j++) {
            $c[$k] = $b[$j];
            $k++;
        }

        var_dump($c);
    }

    public function highway()
    {
        $A = [29, 50];
        $A = [1, 2, 3, 4];
        $B = [1, 2, 3, 4];
        $C = [1, 2, 3, 4];
//        $A = [29, 29];
        $A = [2];
//        $B = [61, 37];
        //  $B = [61, 61];
        $B = [3];
//        $C = [37, 70];
        //  $C = [70, 70];
        $C = [3];

        sort($A);
        sort($B);
        sort($C);

        // var_dump($A, $B, $C);
        $total = 0;

        $lastJ = 0;
        $lastK = 0;
        for ($i = 0; $i < count($A); $i++) {
            for ($j = $lastJ; $j < count($B); $j++) {
                if ($B[$j] > $A[$i]) {
                    // var_dump( $B[$j]);
                    $bCombo = count($B) - $j;
                    for ($k = $lastK; $k < count($C); $k++) {
                        echo "<br> $k <br>";
                        if ($C[$k] > $B[$j]) {

                            //var_dump($C[$k]);
                            // echo $C[$k];
                            $cCombo = count($C) - $k;
                            $total += $bCombo * $cCombo;

                            if ($bCombo * $cCombo > 1000000000 || $total > 1000000000) {
                                var_dump(-1);
                            }
                            break;
                        }

                    }
                    $lastK = $k;
                    echo "lastK " . $lastK;
                    break;
                }
            }
            $lastJ = $j;
            echo "lastJ " . $lastJ;
        }
        echo " total ";
        var_dump($total);
    }

    private function getQuadrant(int $x, int $y)
    {
        if ($x >= 0) {
            if ($y >= 0) {
                return 1;
            } else {
                return 4;
            }
        } else {
            if ($y >= 0) {
                return 2;
            } else {
                return 3;
            }
        }
    }

    public function bob()
    {
        $array = [
            new Obj(-1, -2),
            new Obj(1, 2),
            new Obj(2, 4),
            new Obj(-3, 2),
            new Obj(2, -2),
            new Obj(3, 6),
            new Obj(-40, -80)
        ];
        //  $array = [new Obj(-1,-2)];

        $rays = [];
        foreach ($array as $statue) {
            $q = $this->getQuadrant($statue->x, $statue->y);
            $ratio = $statue->x / $statue->y;
            $rays[$q][$ratio] = true;
        }

        $count = 0;
        foreach ($rays as $quadrant) {
            $count += count($quadrant);
        }

        echo $count;
    }


    public function sum()
    {
        $A = [3, 5, 1];

        $stepen = 1;
        $number = 0;
        foreach ($A as $num) {
            $number += $num * $stepen;
            $stepen *= 10;
        }
        var_dump($number);

        $number *= 17;

        $result = 0;
        while ($number > 0) {
            $result += $number % 10;
            $number = (int)($number / 10);
        }


        var_dump($result);
    }