Store Credit

 

Question

You need to find the products which add up to a credit value from the list of values.

The problem might look very simple. But you need to be careful in deciding what solution to take

Solution

  You need to subtract the credit value with the values in the list. If credit – value in the list is found in the main list of values, then the 2 index just found (one in the main list another in the credit-value list ) are the indexes which add up to the credit.

Better to avoid seeing the below code since it is very simple to make it to code. If you have not succeeded in that too, verify the below code logic.

Code

#include <vector>

#include <iostream>

#include <string>

vector<int> maxcredit(int credit, char* list, int lsize)

{

    int i;

    int* tlist;

    tlist = (int*) malloc(sizeof(int)*lsize);

    std::vector<int> result;

    char* prod = strdup(list);

    char* next = prod;

    i=0;

    strtok(next, " ");

    while(next)

    {

        int key = atoi(next);

        tlist[i] = key;

        next = strtok(NULL, " ");

        ++i;

    }

    free(prod);

    for(int j=0; j <i;j++)

    {

        for(int k=0; k < i; k++) {

            if(k != j && credit-tlist[j] == tlist[k]) {

                result.push_back(j+1);

                result.push_back(k+1);

                return result;

            }

        }

    }

    return result;

}

void main()

{

    ifstream infile("A-large-practice.in");

    ofstream outfile("result.txt");

    string line;

    getline(infile, line);

    int num_of_cases = atoi(line.c_str());

    for(int i=1; i<=num_of_cases; i++)

    {

        getline(infile, line);

        int credit = atoi(line.c_str());

        getline(infile, line);

        int size = atoi(line.c_str());

        getline(infile, line);

        char* list = strdup(line.c_str());

        vector<int> tst = maxcredit(credit, list, size);

        outfile<<"Case #"<<i<<": "<<tst[0]<<" "<<tst[1]<<endl;

        free(list);

    }

}

• Avoid using maps or hash maps as it sorts the keys. If you use the normal index as the key and the second index of credit-value list as value, you will end up getting index in wrong order
• in C++, try to use getline version which doesn’t depend on the buffer size. If you define a buffer size then, our large data set will fail.
• There is no possibility of getting more than two values as we just take k and j on an iteration. The total performance at worst case will be around O(n2).
• Make it a habit to free memory