PHP timeout issues with for loop

Question

I'm trying to solve a PHP problem and what I have put together DOES work for some cases, but with larger values and data sets, it fails due to timeout. I need help determining what can be done to address that.

I'm working on further developing my PHP knowledge, and this problem comes from a test site that I've been using. The problem is essentially there are two people with a combined amount of $money to spend on ice cream. There are an array of flavors, $cost, which are each represented by an integer that is the cost of the flavor. Need to find the two flavors that equal exactly the amount of $money and display those two numbers, not the cost but the number of the flavor. The problem always has a unique solution.

I already filtered so flavors that cost more than the amount of money on their own do not even get checked... and the checking stops after a solution is found.

<?php 

function whatFlavors($cost, $money) {
    $num_flavors = count($cost);
    $select_flavors = array(0);

    for ($i = 0; $i < $num_flavors; $i++) {
        if (($cost[$i] < $money) && ($select_flavors[0] == '0')) {
            for ($j = 1; $j < $num_flavors; $j++) {
                if ($cost[$j] < $money) {
                    if ($cost[$i] + $cost[$j] == $money) {
                        $select_flavors[0] = $i+1;
                        $select_flavors[1] = $j+1;
                        break;
                    } else {
                        $break;
                    }
                }
            }
        }
    }
    sort($select_flavors);
    echo $select_flavors[0]." ".$select_flavors[1]."\n";

}
?>

To run the code with test cases, use:

$stdin = fopen("php://stdin", "r");

fscanf($stdin, "%d\n", $t);

for ($t_itr = 0; $t_itr < $t; $t_itr++) {
    fscanf($stdin, "%d\n", $money);

    fscanf($stdin, "%d\n", $n);

    fscanf($stdin, "%[^\n]", $cost_temp);

    $cost = array_map('intval', preg_split('/ /', $cost_temp, -1, PREG_SPLIT_NO_EMPTY));

    whatFlavors($cost, $money);
}

fclose($stdin);

Test input details: - first line is how many tests are included - second line is how much money is to be spent - third line is how many flavors are included - fourth line is a space separated array of flavors, each represented by their cost

Sample Test Case that DOES work:

2 4 5 1 4 5 3 2 4 4 2 2 4 3

Test Case that TIMES OUT:

Provided by testing site, too long to paste here, so you can grab a text file from this link... https://app.box.com/s/ka01xpigqmvcjflcv0bl9760svdb78vd

Is $break; a typo or are you intending to actually break;? — Will B.
– Will B., Commented May 22, 2019 at 0:40
Please provide some sample data, the expected result of your code, and elaborate more as to when exactly your code is timing out, such as what data is provided to cause it to occur. — Will B.
– Will B., Commented May 22, 2019 at 0:51
I have edited the initial post with more detail. This is on a testing site, so not a server situation. Full details with test cases now included. Thanks! — DirectTech
– DirectTech, Commented May 22, 2019 at 3:54

miken32 · Accepted Answer · 2019-05-22 19:17:49Z

So you're looking for the two array elements that add up to a certain number? You are looping exponentially over every element in your array so it's no wonder you're hitting timeouts.

You only need one loop, to iterate through the array. On each iteration, simple subtraction tells you what value you're looking for. Just use a standard array_search to look for it. Once you find a pair, you can stop looking.

<?php

function whatFlavours($cost, $money) {
    foreach ($cost as $i=>$v) {
        $j = array_search($money - $v, $cost);
        if ($j !== false) {
            return [$i, $j];
        }
    }
    return [0, 0];
}

$cost = [23, 53, 13, 46, 11, 8, 27, 4];
$money = 24;
$result = whatFlavours($cost, $money);
echo "$result[0] $result[1]";

Output:

2 4

i.e. 13 + 11.

Also, you should never echo from a function. Always return a value for use outside the function.

Collectives™ on Stack Overflow

PHP timeout issues with for loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related