C# solution for ‘Store Credit’ from code jam 2010

Problem statement: https://code.google.com/codejam/contest/351101/dashboard

A naive solution to this problem is to repeatedly loop over the previously entered numbers for every input entered by the user. This would have resulted in a nested for-loop so I tried to think of a better solution.

My final solution is one in which the program loops over the list of items only once. How is this achieved? By using a marker array. Each position in this array represents an amount. If position 54 in the marker array contains 4 it means that the 4th item in the input list costs 54.

Here is the algorithm:

  1. Create an array of size ‘credit’.
  2. For every item look for a matching item in the marker array. This ‘matching item’ is an item that costs (credit – cost).
  3. If a match is found then stop.
  4. Otherwise make an entry in the marker array.

Solution

		/// <summary>
		/// Returns a string "A B" where A and B are the two indices whose
		/// price adds up the store credit
		/// </summary>
		/// <param name="items"></param>
		/// <param name="credit"></param>
		/// <returns></returns>
		private static string FindItems(List<Int32> items, int credit)
		{
			//Create an integer array of size 'credit' since we can safely ignore
			//items that cost more than the credit we have
			int[] itemCosts = new int[credit];

			int currentItem;
			for (int i = 0; i < items.Count; i++)
			{
				currentItem = items[i];

				if(currentItem < credit)
				{
					//Find the amount required in order to fill credit with current item
					//and another item
					if(itemCosts[credit - currentItem] != 0)
					{
						return String.Format("{0} {1}", itemCosts[credit - currentItem], i+1);
					}
					else
					{
						itemCosts[currentItem] = i + 1;
					}
				}
			}

			return "";
		}

Full source-code available here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s