Google Code Jam - Store Credit

Below is my answer to the Google Code Jam's answer to the Store Credit. As usual the code run's perfectly well, however, my credit_pos function gives a warning when returning the temp array..


You receive a credit C at a local store and would like to buy two
items. You first walk through the store and create a list L of all
available items. From this list you would like to buy two items that
add up to the entire value of the credit. The solution you provide
will consist of the two integers indicating the positions of the items
in your list (smaller number first).


Input


The first line of input gives the number of cases, N. N test cases
follow. For each test case there will be:

• One line containing the value C, the amount of credit you have at the store.

• One line containing the value I, the number of items in the store.

• One line containing a space separated list of I integers. Each integer P indicates the price of an item in the store.

Each test case will have exactly one solution.

Link to the question

#include 
#include 
#include 
#include 

int * credeit_pos(std::vector v, int n, int credit);

int main(int argc, char ** argv) {

    std::ifstream infile(argv[1]);
    if(!infile) {
        std::cout > num_cases;
    while(i > credit;
        infile >> n_items;
        int price;
        std::vector prices;
        for(int j=0; j> price;
            prices.push_back(price);
        }
        int * loc = credeit_pos(prices, n_items, credit);
        outfile  prices, int n_items, int credit){
    int  temp[2];
    for(int i=0; i<n_items-1; i++){
        for(int j=i+1; j<n_items; j++){
            if(!(prices[i] + prices[j] == credit))
                ;
            else {
                temp[0] = i + 1, temp[1] = j + 1;
            }
        }
    }
    return temp;
}

Leaving alone an UB (which is already addressed), let's look at an actual solution, the credeit_pos function.


From this list you would like to buy two items that add up to the entire value of the credit.

In a programming terms: given a range, find two values which add up to the given value.

The proposed solution is

for each elements in a range,
try to find a peer adding up to a target


It is correct but an implementation has quadratic complexity. It feels wrong. Every time you work with a linear range and end up with a quadratic algorithm, ask yourself if it can be improved if the range was sorted (sort is cheap comparing to quadratic). In this case it can be indeed: finding (or failing to find) a peer in a sorted range is a binary search (\$\log(n)\$), which drives an overall complexity to \$n \log(n)\$.

Summing up, the template is

std::sort(std::begin(prices), std::end(prices));
for (auto it = std::begin(prices); it != std::end(prices); ++it) {
auto peer = std::upper_bound(it, std::end(prices), target - *it);
if (it + peer == credit) return std::make_pair(it, peer);
}


PS: since the problem statement guarantees that the solution exists, I didn't bother to check that peer != end(prices).

PPS: the second phase could be completed in a linear time, but due to presence of sort it doesn't matter here.

StackExchange Code Review Q#59186, answer score: 8