CODEWITHSUNDEEP
c#algorithm
user1108948
user1108948

Reputation:

Pick up two numbers from an array so that the sum is a constant

I came across an algorithm problem. Suppose I receive a credit and would like to but two items from a local store. I would like to buy two items that add up to the entire value of the credit. The input data has three lines.

The first line is the credit, the second line is the total amount of the items and the third line lists all the item price.

Sample data 1:

200
7
150 24 79 50 88 345 3

Which means I have $200 to buy two items, there are 7 items. I should buy item 1 and item 4 as 200=150+50

Sample data 2:

8
8
2 1 9 4 4 56 90 3

Which indicates that I have $8 to pick two items from total 8 articles. The answer is item 4 and item 5 because 8=4+4

My thought is first to create the array of course, then pick up any item say item x. Creating another array say "remain" which removes x from the original array.

Subtract the price of x from the credit to get the remnant and check whether the "remain" contains remnant.

Here is my code in C#.

        // Read lines from input file and create array price
        foreach (string s in price)
        {
            int x = Int32.Parse(s);
            string y = (credit - x).ToString();

            index1 = Array.IndexOf(price, s) ;
            index2 = Array.IndexOf(price, y) ;
            remain = price.ToList();
            remain.RemoveAt(index1);//remove an element
            if (remain.Contains(y))
            {
                break;
            }
        }
        // return something....

My two questions:

  1. How is the complexity? I think it is O(n2).
  2. Any improvement to the algorithm? When I use sample 2, I have trouble to get correct indices. Because there two "4" in the array, it always returns the first index since IndexOf(String) reports the zero-based index of the first occurrence of the specified string in this instance.

Upvotes: 1

Views: 1429

Answers (5)

Riley Foster
Riley Foster

Reputation: 1

I know I am posting this is a year and a half later, but I just happened to come across this problem and wanted to add input.

If there exists a solution, then you know that both values in the solution must both be less than the target sum.

  1. Perform a binary search in the array of values, searching for the target sum (which may or may not be there).

  2. The binary search will end with either finding the sum, or the closest value less than sum. That is your starting high value while searching through the array using the previously mentioned solutions. Any value above your new starting high value cannot be in the solution, as it is more than the target value.

    1. At this point, you have eliminated a chunk of data in log(n) time, that would otherwise be eliminated in O(n) time.

Again, this is an optimization that may only be worth implementing if the data set calls for it.

Upvotes: 0

Vikram Bhat
Vikram Bhat

Reputation: 6246

Here is an algorithm in O(N) time complexity and O(N) space : -

1. Put all numbers in hash table.
2. for each number Arr[i] find Sum - Arr[i] in hash table in O(1)
3. If found then (Arr[i],Sum-Arr[i]) are your pair that add up to Sum

Note:- Only failing case can be when Arr[i] = Sum/2 then you can get false positive but you can always check if there are two Sum/2 in the array in O(N)

Upvotes: 0

Jim Mischel
Jim Mischel

Reputation: 133975

Create a HashSet<int> of the prices. Then go through it sequentially.Something like:

HashSet<int> items = new HashSet<int>(itemsList);

int price1 = -1;
int price2 = -1;
foreach (int price in items)
{
    int otherPrice = 200 - price;
    if (items.Contains(otherPrice))
    {
        // found a match.
        price1 = price;
        price2 = otherPrice;
        break;
    }
}
if (price2 != -1)
{
    // found a match.
    // price1 and price2 contain the values that add up to your target.
    // now remove the items from the HashSet
    items.Remove(price1);
    items.Remove(price2);
}

This is O(n) to create the HashSet. Because lookups in the HashSet are O(1), the foreach loop is O(n).

Upvotes: 2

Irit Katriel
Irit Katriel

Reputation: 3564

This problem is called 2-sum. See., for example, http://coderevisited.com/2-sum-problem/

Upvotes: 1

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

You can simply sort the array in O(nlogn) time. Then for each element A[i] conduct a binary search for S-A[i] again in O(nlogn) time.

EDIT: As pointed out by Heuster, you can solve the 2-SUM problem on the sorted array in linear time by using two pointers (one from the beginning and other from the end).

Upvotes: 4

Related Questions