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 &lt;iostream&gt;
#include &lt;fstream&gt;
#include &lt;cstdlib&gt;
#include &lt;vector&gt;

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

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

    std::ifstream infile(argv[1]);
    if(!infile) {
        std::cout &lt;&lt; "could not open " &lt;&lt; infile &lt;&lt;std::endl;
        exit(EXIT_FAILURE);
    }
    std::ofstream outfile (argv[2]);
    if(!outfile) {
    std::cout &lt;&lt; "could not open " &lt;&lt;outfile &lt;&lt; std::endl;
        exit(EXIT_FAILURE);
    }

    int num_cases, i=0, n_items, credit;
    infile &gt;&gt; num_cases;
    while(i &lt; num_cases){
        infile &gt;&gt; credit;
        infile &gt;&gt; n_items;
        int price;
        std::vector&lt;int&gt; prices;
        for(int j=0; j&lt;n_items; j++){
            infile &gt;&gt; price;
            prices.push_back(price);
        }
        int * loc = credeit_pos(prices, n_items, credit);
        outfile &lt;&lt;"Case #"&lt;&lt; i+1 &lt;&lt;": " &lt;&lt; loc[0] &lt;&lt;" "&lt;&lt; loc[1] &lt;&lt; std::endl;
        i++;
    }
}

int * credeit_pos(std::vector&lt;int&gt; prices, int n_items, int credit){
    int  temp[2];
    for(int i=0; i&lt;n_items-1; i++){
        for(int j=i+1; j&lt;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.