find whether any two list values sum to given value

Question

When I was asked to write a method that would check if any pair in array list is equal to given value, I came up with this:

import java.util.ArrayList;

public class FindWhetherTwoInArrEqual {

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(10);        arr.add(12);
        arr.add(18);        arr.add(10);
        arr.add(8);         arr.add(12);
        arr.add(33);        arr.add(28);
        arr.add(2);         arr.add(20);
        findWhetherTwoInArraySumToValue(arr, 30);
    }
    public static boolean findWhetherTwoInArraySumToValue(ArrayList<Integer> array, int value)
    {
        for(int i = 0; i < array.size(); ++i)
            for(int j=i+1; j < array.size(); ++j)
                if(array.get(i) + array.get(j) == value)               
                    System.out.println(array.get(i) +" + "+ array.get(j) + " = " + value); 
        return false;
    }    
}

Result:

10 + 20 = 30
12 + 18 = 30
18 + 12 = 30
10 + 20 = 30
28 + 2 = 30

The time complexity is O(n).

Is there more efficient way of doing this?

This isn't an algorithmic but rather an implementation comment: I'd cache `array.get(i)` and `array.get(j)` to variables. The JIT can probably do that for you, but you *know* you can do it, so... If you scope them right, you can even make them `final` as an added hint to the JIT. Example: http://pastie.org/8626976 — T.J. Crowder, Jan 12 '14 at 18:13
Order N: One pass to find out what values you've got, another pass to find out how many of them have a matching (30-n) value. — keshlam, Jan 12 '14 at 18:15
possible duplicate of [find pair of numbers in array that add to given sum](http://stackoverflow.com/questions/8334981/find-pair-of-numbers-in-array-that-add-to-given-sum) — MrSimpleMind, Jan 12 '14 at 18:15
This is not linear, but quadratic time. With a hashset you could easily get linear. — Marko Topolnik, Jan 12 '14 at 18:25

score 1 · Answer 1 · answered Jan 12 '14 at 18:25

Assuming that the pair does NOT need to occur in a certain order, You could do this:

#1 Sort the pair and assume A is the least in the pair and B is the greatest in the pair
#2 Quicksort the array: See this URL:
http://gauss.ececs.uc.edu/Courses/C321/html/quicksort.java.html
#3 Start looking for A in the sorted array. As soon as an element that is greater occurs, there is no match.
#4 Start looking for B in the sorted array. As soon as an element that is greater occurs, there is no match.
#5 If #3 and #4 are both matches, the pair is in the array.

score 1 · Answer 2 · answered Jan 12 '14 at 18:35

I don't know if it's faster and bear with me because i'm only 15, but I think You can calculate which number is the pair for each element in the array, then you check if it is in the array. At least it looks simpler(for me) Ex.:

public static boolean findWhetherTwoInArraySumToValue(ArrayList<Integer> array, int value)
{
    for(int element : array){
        int find = element - value;
        if(array.contains(find)){
            System.out.println(element +" + "+ find + " = " + value);
        }
    }
    return false;
}

Good thought, though .contains() for an array is a linear search so it doesn't improve things. You're on the right track, though; once you've copied the values into something like a hashshet, which can run .contains() much more quickly, this *is* an improvement. — keshlam, Jan 12 '14 at 18:37

score 1 · Answer 3 · answered Jan 12 '14 at 18:35

Order-N, as Marko pointed out:

Pass 1: Determine what values you have. Hashset by value, or tickmarks in a 30-element array (assuming you don't have negatives), or some other fast-retrieval mechanism.

Pass 2: Start with found=0. For each value, check the table to see if it contains 30-value. If so, increment found.

Return found>1.

Kailash · Accepted Answer · 2014-01-13T07:21:42.780

1

Can you try this code :

 for(int i =0;i< array.size(); ++i){
        if(array.contains(value - array.get(i)))
        {
            System.out.println((value - array.get(i)) +" + "+ array.get(i) + " = " + value);
        }
    }

edited Jan 13 '14 at 07:21

answered Jan 12 '14 at 21:23

Kailash

642
2
9
15

find whether any two list values sum to given value

4 Answers4