# 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.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>

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

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

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

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

int * credeit_pos(std::vector<int> 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;
}

-
If you recall from one of my earlier answers, you should return EXIT_FAILURE, not call exit(). The error message should also be sent to cerr, not cout. –  Jamal Aug 6 '14 at 2:48
Yeah, Got that. Thanks! –  Sam Obeng Aug 6 '14 at 3:03

If this is working for you, it is purely due to luck. This program actually has undefined behavior, specifically returning the address of a local variable. As you've noticed, your compiler gives you a warning about this:

In function 'int* credeit_pos(std::vector, int, int)':

What is actually happening here is, when the function is called, it allocates some space on the stack for the temp array (specifically, 2 * sizeof(int)) in this case. When the function returns, this space is "reclaimed" (by adjusting the stack pointer). It is running without error for you because you don't have any other function calls between when you call this function and when you use the result. This is still extremely dangerous, however.

This is one of the many reasons C++ programmers will recommend that you do not use raw arrays and raw pointers; these sort of traps are all too easy to fall into. Generally, you should replace this with either a std::vector, or a std::array. In this case, you can actually just use a std::pair, which is a container that holds two values.

A further thing to look out for is passing things by value vs passing by reference. Here, when you pass the prices vector, you are creating an (unnecessary) full copy. This should be passed by const & instead:

Your logic is somewhat confusing: if prices[i] + prices[j] != credit then keep going, otherwise write to temp. This should just be a single if:

if(prices[i] + prices[j] == credit) {
// logic
}


Some other minor points:

Whitespace around operators is usually a good thing. I personally find this hard to read:

for(int i=0; i<n_items-1; i++);


for(int i = 0; i < n_items - 1; ++i);


Putting multiple statements on one line using , is generally a bad idea, it can end up causing all sorts of problems:

 temp[0] = i + 1, temp[1] = j + 1;


Try to limit yourself to one statement per line:

 temp[0] = i + 1;
temp[1] = j + 1;


This is how the function looks with these modifications (note you'll need an #include <utility> for std::pair).

std::pair<int, int> credit_pos(const std::vector<int>& prices, int n_items, int credit)
{
std::pair<int, int> temp;
for(int i = 0; i < n_items - 1; ++i) {
for(int j = i + 1; j < n_items; ++j) {
if(prices[i] + prices[j] == credit)
temp.first = i + 1;
temp.second = j + 1;
}
}
}
return temp;
}

-
Thanks for your feedback. At first, i declared temp to be a vector but i changed my mind since it only needed to store just two values. Thanks for pointing out to my lack of programming best practices. Old practices die hard, and i hope to get used to the spacing and other similar things you mentioned. –  Sam Obeng Aug 6 '14 at 1:39

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.

-
+1 but i have some doubts, with the application of upper_bound. what did you expect to be target. obviously it cannot be credit since *peer > target - *it makes *it + *peer > target. one more thing, after sorting how do you suppose to find the original indices of the matching pair (as the output should be it) –  Anubis Apr 3 at 5:20

This doesn't need to be a while loop:

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


You're already using a for loop inside of this larger loop, which is the same thing.

You also have i=0 squeezed into this line:

int num_cases, i=0, n_items, credit;


(@Yuushi has already mentioned having separate lines, so I won't repeat that.)

Take that out, along with the i++ in the loop, and put them into another for loop:

for (int i = 0; i < num_cases; i++) {
infile >> credit;
infile >> n_items;

int price;
std::vector<int> prices;

for (int j = 0; j < n_items; j++) {
infile >> price;
prices.push_back(price);
}

int * loc = credeit_pos(prices, n_items, credit);
outfile << "Case #" << i+1 << ": " << loc[0] << " " << loc[1] << std::endl;
}


(I've also incorporated @Yuushi's whitespace advice here.)

-
what is the difference (replacing while loop with for-loop)? Any penalty for using a while loop? –  Sam Obeng Aug 6 '14 at 3:08
@SamObeng: No penality per se. It's just more concise and better communicates its intention. However, if i didn't change constantly (for instance, a condition must be met in order to increment i), then you should use a while loop. –  Jamal Aug 6 '14 at 3:11
@Jamal: Ternary operator ?: works on java. If that's the case also in c++, i+=(condition)?1:0 can be used as well. –  bunyaCloven Aug 6 '14 at 6:45
@bunyaCloven: What about the ternary operator here? –  Jamal Aug 6 '14 at 15:22
You can use it in a for loop while you cannot use if instead –  bunyaCloven Aug 6 '14 at 15:35