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.


		/// <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);
						itemCosts[currentItem] = i + 1;

			return "";

Full source-code available here.


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s