The Algorithm Design Manual 4-6

Given two sets S1 and S2 (each of size n), and a number x, describe an O(n log n) algorithm for finding whether there exists a pair of elements, one from S1 and one from S2 , that add up to x. (For partial credit, give a Θ(n2) algorithm for this
problem.)

package avdongre.tadm;

import java.util.Arrays;

public class TwoSetFindElementWithSum {
	private class Pair<FIRST, SECOND> {
		public FIRST first;
		public SECOND second;

		public Pair(FIRST x, SECOND y) {
			first = x;
			second = y;
		}

		@Override
		public String toString() {
			return String.format(first + "," + second);
		}
	}

	private int binarySearch(int[] input, int key) {
		int left = 0;
		int right = input.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			if (key < input[mid]) {
				right = mid - 1;
			} else if (key > input[mid]) {
				left = mid + 1;
			} else {
				return input[mid];
			}

		}
		return Integer.MAX_VALUE;

	}

	public Pair<Integer, Integer> solveTwoSetFindElementWithSum(int[] input1,
			int[] input2, int target) {	

		Arrays.sort(input2); // n log n
		// iterate over the input1 and search for target - input[i]
		// using binary search so this will be
		// n times logn
		// nlogn + nlogn will be order of the solution.

		for (int i = 0; i < input1.length; i++) {
			int val = binarySearch(input2, target - input1[i]);
			if (val != Integer.MAX_VALUE) {
				return new Pair<Integer, Integer>(input1[i], val);
			}
		}
		return new Pair<Integer, Integer>(Integer.MAX_VALUE, Integer.MAX_VALUE);

	}

	public static void main(String[] args) {
		TwoSetFindElementWithSum s = new TwoSetFindElementWithSum();
		{
			int[] input1 = new int[] {};
			int[] input2 = new int[] {};
			System.out.println(s.solveTwoSetFindElementWithSum(input1, input2,
					0));
		}
		{
			int[] input1 = new int[] {1,5,7,3,9,4};
			int[] input2 = new int[] {6,2,1,7,4,10};
			System.out.println(s.solveTwoSetFindElementWithSum(input1, input2,
					13));
		}		
		{
			int[] input1 = new int[] {10, 50, 40, 30, 20};
			int[] input2 = new int[] {60, 90, 80, 70};
			System.out.println(s.solveTwoSetFindElementWithSum(input1, input2,
					100));
		}		

	}

}

Advertisements

One thought on “The Algorithm Design Manual 4-6

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