Finding the indices of the two items whose price adds up to to a value

Question

I've solved the Google Jam store credit problem. but there's some inefficiencies that I want to get rid of them to improve the algorithm and reduce the multiple iteration. What are other better ways to do so?

Problem:

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.

Output:

For each test case, output one line containing "Case #x: " followed by the indices of the two items whose price adds up to the store credit. The lower index should be output first.

Limits

5 ≤ C ≤ 1000 1 ≤ P ≤ 1000

Small dataset

N = 10 3 ≤ I ≤ 100

Large dataset

N = 50 3 ≤ I ≤ 2000

Solution:

#!/usr/bin/env python3.4
import sys
from itertools import combinations, count

cases = []
credits = []
items = []

with open(sys.argv[1]) as file_:
    next(file_)
    cases = (list(zip(*[file_]*3)))

for case in cases:
    credits.append(int(case[0]))
    items.append([int(item) for item in case[2].split()])

for credit, prices, i in zip(credits, items, count()):
    for tow_items in combinations(prices, 2):
        if sum(tow_items) == credit:
            print("Case #{}:".format(i+1), end=' ')
            print(' '.join([str(i+1) for i, price in enumerate(prices)
                            if price in tow_items]))

Answer 1

Code organisation

Instead of building cases, then use it to build credits and items then use them to fix the problem, you could do things in a more straightforward way with less temporary containers.

with open(sys.argv[1]) as file_:
    next(file_)
    for i, case in enumerate(zip(*[file_]*3)):
        credit = int(case[0])
        prices = [int(item) for item in case[2].split()]
        for tow_items in combinations(prices, 2):
            if sum(tow_items) == credit:
                print("Case #{}:".format(i+1), end=' ')
                print(' '.join([str(i+1) for i, price in enumerate(prices) if price in tow_items]))

Also, it would probably make sense to split your code into multiple functions : you could write a function handling input/ouput and a function to handle the algorithmic part of the problem.

def get_indices_with_sum(prices, credit):
    for tow_items in combinations(prices, 2):
        if sum(tow_items) == credit:
            return [i for i, price in enumerate(prices) if price in tow_items]
    assert False  # Is not suppose to happen

def run_on_file(filename):
    with open(filename) as file_:
        next(file_)
        for i, case in enumerate(zip(*[file_]*3)):
            credit = int(case[0])
            prices = [int(item) for item in case[2].split()]
            j, k = get_indices_with_sum(prices, credit)
            print("Case #{}: {} {}".format(i+1, j+1, k+1))

run_on_file(sys.argv[1])

Now, different great things are easily doable : - you can your call to run_on_file behind an if __name__ == "__main__": guard to have reusable code on one hand (you could need the get_indices_with_sum function to solve other problems) and code actually doing something on the other hand. - you can write tests to check your code automatically. The great thing is that the problem description gives you a few examples.

def unit_tests():
    j, k = get_indices_with_sum([5, 75, 25], 100)
    assert (j, k) == (1, 2)
    j, k = get_indices_with_sum([150, 24, 79, 50, 88, 345, 3], 200)
    assert (j, k) == (0, 3)
    j, k = get_indices_with_sum([2, 1, 9, 4, 4, 56, 90, 3], 8)
    assert (j, k) == (3, 4)


if __name__ == "__main__":
    unit_tests()
    # run_on_file(sys.argv[1])

At this step, your code is already better but we haven't improved performance. We've only make improvements easier to write and to test.

Algorithm

In order to write a faster algorithm, I am assuming we are interested in the case when we are given a store with a huge number of elements n (called I in the problem description).

At the moment, you (potentially) iterate over all combinations and there are n * (n-1)/2. Assuming you always find what you are looking for, we may assume that you go through n * (n-1) / 4 combinations in average. Then, when the solution is found, your iterate once more over prices so you roughly perform n + n * (n-1) / 4 operations. We usually keep only the asymptotic behavior of the program and remove the constant factor and say that your program is 'O(n^2)'.

You could try to run your program with bigger and bigger inputs and see the time it takes. Usually when you take a input twice as big, your algorithm will take 4 times as much time.

If you want to give it a try, I've tweaked the original test to add the following cases (adding elements costing 101 in the store doesn't change what you can get with 100 dollars):

nb_added_elements = 10000
j, k = get_indices_with_sum([101] * nb_added_elements + [5, 75, 25], 100)
assert (j, k) == (nb_added_elements + 1, nb_added_elements + 2)
j, k = get_indices_with_sum([5, 75, 25] + [101] * nb_added_elements, 100)
assert (j, k) == (1, 2)

The problem you are trying to solve is pretty common and has a O(n) solution on a sorted array (you'll find explanations looking for "array find pair sum" in our favorite search engine).

Your case is slightly more complicated because the array is not sorted and sorting it would cause a mess in the indices.

Many solutions are possible : either build an array with value and index before sorting it by value and/or keep a copy of the unsorted array so that you can find its initial position back at the end.

The resulting solution is likely to be O(n*log(n)) because of the sorting (other operations such as lookup/copy and obviously the proper algorithm are only O(n) and as such considered negligeable).

Other details

count and enumerate can be given a starting position (defaulting to 0) so that you don't have to add 1 yourself if you want to count from 0.

Answer 2

Here's the solution that I end up with:

#!/usr/bin/env python3.4
# filename: store_credit.py
import sys


def find_two_items_with_sum(list_, sum_):
    hash_ = {}
    for i, element in enumerate(list_, 1):
        if sum_ - element in hash_.keys():
            for t in hash_[sum_ - element]:
                return t, i

        if element in hash_.keys():
            hash_[element].append(i)
        else:
            hash_[element] = [i]

if __name__ == '__main__':
    with open(sys.argv[1]) as file_:
        next(file_)
        for i, case in enumerate(zip(*[file_]*3), 1):
            credit = int(case[0])
            prices = [int(item) for item in case[2].split()]
            tow_items = find_two_items_with_sum(prices, credit)
            print("Case #{}: {} {}".format(i, *tow_items))

Test:

from store_credit import find_two_items_with_sum
# filename: test_store_credit.py


def test_that_it_finds_indices_that_adds_up_to_sum():
    """ Test that it can find indices of the two items
    whose value adds up to a given value.
    """
    j, k = find_two_items_with_sum([5, 75, 25], 100)
    assert (j, k) == (2, 3)
    j, k = find_two_items_with_sum([150, 24, 79, 50, 88, 345, 3], 200)
    assert (j, k) == (1, 4)
    j, k = find_two_items_with_sum([2, 1, 9, 4, 4, 56, 90, 3], 8)
    assert (j, k) == (4, 5)

Details:
O(n) Method using Hash Table.

For unsorted array, by using extra space we can solve the problem in O(n) time. We maintain a hash table to hash the scanned numbers. We scan each numbers from the head to tail, when we scan the i-th number y, we do following steps:

1. Check if (x-y) is hashed.
2. If hashed, print out (j,i) where j is the elements of the hashed value with index (x-y).
3. Add (key=x-y, value=i) into the hash table.

Therefore, the time complexity is O(n) and the space complexity is O(n).

Resources:
Find a pair of elements from an array whose sum equals a given number
Find two numbers in an array whose sum is x