Google Code Jam Practice Problem – Store Credit

Problem is described at Store Credit

Analysis
This is variation of the problem where you have you have unsorted array of integers and sum K. You need to find two numbers from the array whose sum is K

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	private static void solve(int credit, int numOfItems, int[] items) {
		// Map has key[i] = item[i]
		// and value[i] = Index of Item in items array + 1
		Map<Integer, Integer> itemToCreditSum = new HashMap<Integer, Integer>();
		for (int i = 0; i < numOfItems; i++) {
			if (itemToCreditSum.get(credit - items[i]) != null) {
				System.out.println(itemToCreditSum.get(credit - items[i]) + " "
						+ (i + 1));
				break;
			} else {
				itemToCreditSum.put(items[i], i + 1);
			}
		}
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			// Read credit
			int C = Integer.parseInt(stdin.nextLine());
			// Number of Items in the store
			int I = Integer.parseInt(stdin.nextLine());
			// Create item array
			int[] items = new int[I];
			// Read the items values
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			for (int j = 0; j < I; j++) {
				int item = Integer.parseInt(next_split[j]);
				items[j] = item;
			}
			System.out.print("Case #" + (i + 1) + ": ");
			solve(C, I, items);
		}
	}

}

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