Explore BrainMass

Sum of 2 Numbers from a Set in O(n log n) Algorithm

Lubo and Mike are building a "do all" robot in CS148 and have found that they have to fit two lego pieces side by side into an opening. The opening is x inches wide and the sum of the widths of the two pieces has to be exactly equal to the width of the opening, otherwise, their robot will fall apart during the demo. They have a huge collection of lego pieces of varying widths at their disposal and have to pick two pieces which satisfy the above constraint.

Since the Computer Science department at Brown believes in doing every- thing through a well defined algorithm, you should supply these poor guys an algorithm for doing the task, and one that is asymptotically efficient! So, here goes your exact problem.

You are given a set of n real numbers and another real number x. Describe a O(nlogn)-time algorithm that determines whether or not there exist two elements in S whose sum is exactly x. Hint : Doesn't the O(n log n) term make you feel that sorting is involved in some way?

Solution Preview

Yes it is done by sorting

I assume that you have some familiarity with algorithms.

First, let us note, that if you look at a particular Lego piece of length y, you can
calculate what should be the length of another piece to complement it:
it should be (x-y).

Every piece can be either primary or complementary.
Therefore, if we can arrange so that we sort some structures in which every piece enters in two copies of a suitably defined structure, in one with its length (y), and in another with its complementary length (x-y), we can find a needed couple in O(n log n) moves, because a matching couple, if any exists, would be one next to another in the sorted list.

Here is an example of how to organize such structures for actual programming.

Let the structure be

struct Triplet {
int Length ;
bool bPrimary ;
int ID

Here, the ID is just the number of the block needed to find it again if you want it,
and the couple (Length, bPrimary) can be either

(y, ...

Solution Summary

This solution discussed how you can arrange to sort to sort the legal structure for actual programming, defines the comparison, sorts the structures and provides an example for the coding using the lego blocks of hypothetical length. This solution is 736 words.