Purchase Solution

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

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
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.

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 ...

Purchase this Solution
Free BrainMass Quizzes
C# variables and classes

This quiz contains questions about C# classes and variables.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

C++ Operators

This quiz tests a student's knowledge about C++ operators.

Basic Networking Questions

This quiz consists of some basic networking questions.

View More Free Quizzes
Related BrainMass Solutions

  • Linear Equations, Inequalities and Word Problems

    Two numbers with the sum of 12 Let x,y be two number then x+y=12 Even integers. Find two consecutive even integers that have a sum of 450.

  • Working with Parseval's Theorem

    we get: (1.9) And from the orthothonormality relations we see that rightmost sum in (1.8) is: (1.10) While the only surviving term in the left sum is the one when , hence: (1.11) So we obtain: (1.12)   It is easy to see that

  • Find two integers such that their sum is -1

    80901 Find two integers such that their sum is -1 and the sum of their squares is 61. Find two integers such that their sum is -1 and the sum of their squares is 61. Let call the two integers a and b.

  • Explaining the Sum of a Sequence

    If the given terms are even numbers then we can calculate the sum of that even integers using the formula N(N+1). 5) Give an example of the problem. Suppose u r given the problem Find 2+4+6+8. 1.

  • A word problem dealing with two consecutive integers.

    20775 Find the Integers The sum of two consecutive odd integers is 1472. Find the two integers. We need two consecutive integer ODD numbers.

  • Two distinct integers in A whose sum is 104

    43320 Two distinct integers in A whose sum is 104 Let A be any set of twenty integers chosen from the arithmetic progression 1, 4, 7, ...,100. Prove that there must be two distinct integers in A whose sum is 104.

  • Pseudocode to check if sum of 2 items in an array is 100

    73185 Pseudocode to check if sum of 2 items in an array is 100 Write and explain the pseudocode to check whether there are 2 items in an array of n integers so that their total is 100. Hi, This is Leela Krishna.

  • Integer problems

    For any integer b in X, since b<=n, we can find some k such that kb is between n+1 and 2n. But this kb does not belong to Y. This means we can find x integers between n+1 and 2n.

  • consecutive sums

    Suppose a number (a positive integer) N is given, and we'd like to determine whether N can be written as a sum of two consecutive positive integers, say; call them x and x + 1.

View More Related Solutions