This was an interview question that I was asked to solve: Given an unsorted array, find out 2 numbers and their sum in the array. (That is, find three numbers in the array such that one is the sum of the other two.) Please note, I have seen question about the finding 2 numbers when the sum (int k) is given. However, this question expect you to find out the numbers and the sum in the array. Can it be solved in O(n), O(log n) or O(nlogn)

There is a standard solution of going through each integer and then doing a binary search on it. Is there a better solution?

```
public static void findNumsAndSum(int[] l) {
// sort the array
if (l == null || l.length < 2) {
return;
}
BinarySearch bs = new BinarySearch();
for (int i = 0; i < l.length; i++) {
for (int j = 1; j < l.length; j++) {
int sum = l[i] + l[j];
if (l[l.length - 1] < sum) {
continue;
}
if (bs.binarySearch(l, sum, j + 1, l.length)) {
System.out.println("Found the sum: " + l[i] + "+" + l[j]
+ "=" + sum);
}
}
}
}
```

This is very similar to the standard problem `3SUM`

, which many of the related questions along the right are about.

Your solution is `O(n^2 lg n)`

; there are `O(n^2)`

algorithms based on sorting the array, which work with slight modification for this variant. The best known lower bound is `O(n lg n)`

(because you can use it to perform a comparison sort, if you're clever about it). If you can find a subquadratic algorithm or a tighter lower bound, you'll get some publications out of it. :)

Note that if you're willing to bound the integers to fall in the range `[-u, u]`

, there's a solution for the `a + b + c = 0`

problem in time `O(n + u lg u)`

using the Fast Fourier Transform. It's not immediately obvious to me how to adjust it to the `a + b = c`

problem, though.

You can solve it in `O(nlog(n))`

as follows:

Sort your array in `O(nlog(n))`

ascendingly. You need 2 indices pointing to the left/right end of your array. Lets's call them `i`

and `j`

, `i`

being the left one and `j`

the right one.

Now calculate the sum of `array[i] + array[j]`

.

- If this sum is greater than
`k`

, reduce`j`

by one. - If this sum is smaller than
`k`

. increase`i`

by one.

Repeat until the sum equals `k`

.

So with this algorithm you can find the solution in `O(nlog(n))`

and it is pretty simple to implement

Sorry. It seems that I didn't read your post carefully enough ;)

Similar Questions

I had an exam question asking the solution to find how many consecutive numbers in the arithmetic series n, n*2, n*3, n*i ( where i is array length - 1 ) are in an array of random numbers. The numbers

I'm trying to convert a function in java to pl/pgsql, and one problem that I found is when I'm trying to sum 2 negative numbers, and a get a positive number, more specifically : public void sum(){ int

I have been practising algorithmic questions and I came across this one. Given an array(of both +ve and -ve) numbers, I have to find a contiguous subarray such that, the sum is divisible by any number

How to find the sum of all values from two different arrays in Perl? @array1 = (1, 2, 3); @array2 = (10, 10, 10); @sumofarray1and2 = ? So I figured I can do two kinds of things here. I can do two for

I want to sum array in same key and different value. Array ( 0 => Array ( 'locker_id' => 3, 'locker_model' => 1, 'qty' => 2 ), 1 => Array ( 'locker_id' => 3, 'locker_model' => 1,

Given an array of numbers, find out if 3 of them add up to 0. Do it in N^2, how would one do this?

I have this array of strings private static String[] colorsArray = { #bde876, #ff8581, #ffc472, #faed75, #a8c9e5, #999999, #e3a8e5, #dddddd, #fc603c, #ffcc00, #74e8d4, #3cd6fc

How to find the integer occurring maximum number of times (mode) in an unsorted array of integers? One O(nlogn) approach I could think of is to sort. Is there any other better approach?

9 numbers. Count how often the sum of 3 consecutive numbers in this set of numbers equaled to 16: 2, 7, 7, 1, 8, 2, 7, 8, 7, The answer is 2. 2 + 7 + 7 = 16 and 7 + 1 + 8 = 16 But I can't seem to ge

This was given to me in a recent programming interview. I am given an unsorted array of integers with negative and positive values, and required to sort them but only for the positive values. I was wo

Given an array x of length n, and a set of arrays S such that each array in S has length n, find a maximal size set of arrays G in S such that for all 1 <= i <= n, x[i] >= sum(g[i]) for all g

Suppose there is a given number we should test if it is product of four consecutive numbers? So if y is our given number we should test if y = x(x+1)(x+2)(x+3) for any arbitrary x? How to design an al

I have an array and its length is X. Each element of the array has range 1 .. L. I want to iterate efficiently through all array combinations that has sum L. Correct solutions for: L = 4 and X = 2 1 3

As mentioned in the title, I want to find the pairs of elements whose difference is K example k=4 and a[]={7 ,6 23,19,10,11,9,3,15} output should be : 7,11 7,3 6,10 19,23 15,19 15,11 I have read the

what the best simple elegant way to sum number in ksh or bash my example is about let command , but I want to find better way to summary all numbers for example num1=1232 num2=24 num3=444 . . . let SU

Can someone suggest an algorithm that finds all Pythagorean triplets among numbers in a given array? If it's possible, please, suggest an algorithm faster than O(n2). Pythagorean triplet is a set {a,b

I've been studying ruby and have been taking some exercises to see how much I have learned and I've come across this: Q: Write a method, sum which takes an array of numbers and returns the sum of the

I was trying to write a program for the problem I mentioned above, the numbers (i.e the lists) can be of unequal length, I was not able to figure out a way to do this other than the most commonly thou

In this code fragment i can't sum a and b : String a= txtnum1.getText(); String b= txtnum2.getText(); JOptionPane.showMessageDialog(null,a+b); ...because a and b defined by String so this code work l

I have an unsorted array of objects. I need to know how I can sort my array in descending order, according to the highest value inside the objects. I need to do this using for loops, not the easy way.

This question already has an answer here: How to count possible combination for coin problem 12 answers I have given an array.And i want to find the all permutation of an array so it sum to a s

I'm new to java and I have to find the sum of a 2D array but my code simply won't compile. I keep getting the errors : 3 errors found: File: C:\Users\Brett\Documents\DrJava\Matrix.java [line: 9] Error

I have a 2 dimensional array. The rows and columns are sorted. How to find the kth largest element from the 2-d array?

I want to form an array containing indices of k smallest values in an array: import heapq import numpy as np a= np.array([[1, 3, 5, 2, 3], [7, 6, 5, 2, 4], [2, 0, 5, 6, 4]]) [t[0] for t in heapq.nsmal

In Java, how should I find the closest (or equal) possible sum of an Array's elements to a particular value K? For example, for the array {19,23,41,5,40,36} and K=44, the closest possible sum is 23+19

Assume that we have an array of small (about 10^(-15) ) double numbers in c++. If we calculate the sum of numbers in this array sequentially, for example double sum = 0; for (int i = 0; i < n; i++

I'm rather new to Haskell. The problem is to find the sum of all even Fibonacci numbers not greater than 4 million. I can't use lists. If I understand correctly, the below solution is wrong, because

Given an array of length N. How will you find the minimum length contiguous sub-array of whose sum is S and whose product is P. For eg 5 6 1 4 6 2 9 7 for S = 17, Ans = [6, 2, 9] for P = 24, Ans = [4

$a = array(2, 4, 6, 8); echo sum(a) = . array_sum($a) . \n; //==20 how i can do this in java?

my code: foreach($comment as $key => $value) { $total = $value['likes']; echo $key: $total\n } Outputs: 0: 3 1: 18 2: 72 3: 0 4: 10 5: 0 6: 0 7: 0 8: 0 9: 0 10: 0 11: 19 12: 0 13: 0 14: 14 15:

I am quite new in Java and I am asked to finish some certain tasks from my school. I have to create a program where it asks the user to enter numbers (as many as the user wants) But the entering numb

I'm trying to find, for a list of numbers from 1 to 50, what numbers within that range are the sums of two other specific numbers from another list. The other list is 1, 2, 4, 6, 18, 26. I'm basically

I need to find the biggest sum and it containing numbers and whether the first or second number out of two was bigger. How to find it? Let's say that n=10, the two put numbers are 6 and 2, followings:

what is the appropriate Method to get the sum of the 2 largest values in array- using ruby? i knew array.sort and array.max and inject(:+) but don't know how to combine bet them

I need to find consecutive numbers in an array and return a string which tells the range and numbers that don't form a range. I found some of the already asked questions but none of them is in VB.Net:

This question already has an answer here: Find a pair of elements from an array whose sum equals a given number 15 answers I recently came across an interesting Java Algorithm statement Given a

I want to know how I can implement a better solution than O(N^3). Its similar to the knapsack and subset problems. In my question N<=8000, so i started computing sums of pairs of numbers and stored

Given an array of integers, which can contain both +ve and -ve numbers. I've to maximize the product of any 3 elements of the array. The elements can be non-contiguous. Some examples: int[] arr = {-5

Hi my question is how do I display all the numbers in my 2 dimensional array. I only manage to display the total sum of all the number of my array. If you could help me I be very thankful. int[,] A =

I'm a beginner in Java, and NetBeans. I'm trying to make a simple program where you introduce 2 numbers and their sum gets divided by two. However, I'm using JFormattedTExtFields and I don't know how

I have qurey like below $select=$db->select() ->from(array('u'=>'users'),array('u.id','u.business_name','u.user_name', 'u.first_name', 'u.last_name', 'u.email','u.address', 'u.created_date','

I have this array : var type = [Petrol, Petrol, Transport, Petrol, Transport, Personal]; var price = [100,250,50,25,10,20]; Basically type[0] and price[0] is type and its price. Petrol =

Suppose there is an array of size N (N is always even). Given all the elements of the array form a pair,which gives the same sum when added. Find the sum. This is definitely not homework. For example

It's an interview question. Given a number n, find out how many numbers have digit 2 in the range 0...n For example , input = 13 output = 2 (2 and 12) I gave the usual O(n^2) solution but is ther

I am trying to solve a Image matching problem by comparing the average color of pixels present in both the source and pattern image. I have reduced this problem to a sub array sum problem, but cannot

I need the second maximum element in an unsorted array in one iteration. eg: the array is 3 9 8 2 0 -4 87 45 3 2 1 0 The answer should be 45 , its very simple to find max element in one iteration , bu

Possible Duplicate: Easy interview question got harder: given numbers 1..100, find the missing number(s) *No, it is a duplicate !!! some numbers in the given array may be duplicated. Please refer to

Can any one explain why the time complexity for generating a binary heap from a unsorted array using bottom-up heap construction is O(n) ? (Solution found so far: I found in Thomas and Goodrich book t

This question already has an answer here: How to find the kth largest element in an unsorted array of length n in O(n)? 21 answers I'm trying to find the N-th largest element in a large 2-D arr

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn