Find two integers in a set that sum to given value.

Suppose you are given a set P of integers and another integer x. We wish to use a O(n*lg n) algorithm to decide whether there are 2 integers in P whose sum equals to x. Show your algorithm. You can use pseudo code or verbose description to explain your algorithm.

If you need to use any well known standard algorithm in your solution, you need not give details of that, just mention how that is helping you in devising solution for the given problem.

Note that there is no restriction on integers in set P and integer x, that is, we are not restricting ourselves to positive or negative integers.

Solution Preview

We can use following steps to achieve the goal.

Step 1: Sort the given set P using Merge Sort algorithm, that has the time complexity (average and worst-case performance) of O(n*lg n), where n is the number of elements in set P.

Let us say that we sorted the given set in increasing order. After this step, when we are referring to set P, we mean the sorted set P and not the original set P.

Step 2: Now we go over the sorted set elements, current element referred to as Pi, from smallest to the largest ...

Solution Summary

Solution proceeds in conversational style and instead of giving a flat pseudocode, it gives verbose algorithm mixed with complexity analysis explanations. Idea is to help the reader understand the logic that he can express in his own words.

... i value 1 to n-1 until a pair is found whose sum... whether there are 2 items in an array of n integers so that ... Begin set foundflag to 0 For index1 = 1 to n-1 For ...

... A[1] >= A[2] >= > A[n-1], t is a positive integer. We want to find a subset of A, such that the sum... SubSetSum(A, t, S) BEGIN 1. Set S = {}; 2. For i = 0 ...

Write a C++ program to read in a set of numbers from an ... Function to find the deepest ... struct node* deepest(struct node* root, int *depth) { if (root == NULL ...

... certain properties, and then proceeds to find smaller (in ... is a smallest (in absolute value) integer, namely zero. ... proof, you first assume that a set of numbers ...

... for F(2) nF(int) op-value for F(int) rx. ... The test for significant interaction can be found in the ANOVA ... effects of the levels of sales pitch by setting a = .05 ...

... If your answer is not an integer, round your ... of the observations in the data set fall within ... that these ages constitute an entire population, find the standard ...

... number of 5-element subsets of a 9-element set is C ... 1, 2), (2, 3), (3, 5), (4, 7)}, find g ◦ f ... be the integer sequence defined recursively by a. a1 =0; and b ...

... the temperature dropped at a constant rate, find the hourly ... a) Which of the following numbers are integers? ... and minimum values of the following set of numbers. ...

...Find two consecutive integers such that the sum of 2 times the first integer and 4 times second integer is 46. ... It also explains how to set up the equations to ...