Remove elements from HashSet on iteration

Question

Suppose I have a HashSet:

[1, 2, 3, 4, 5, 6]

I want to iterate over it in such a way, that for a given sum, say 6, while iterating over the elements, if I find 2 elements in the Set having sum = 6, I want to remove the other one. E. g., if I am iterating over 1, I should remove 5. I was trying to do something like this:

HashSet<Integer> hs = new HashSet(arr);
int sum = 6;
for(int num : hs) {
    if(hs.contains(sum - num)) {
        hs.remove(sum - num);
    }
}

Obviously it throws java.util.ConcurrentModificationException. Another approach is to use iterator but it removes the current element and does not take any other element as parameter. What else can I use?

Update: I know the techniques to use an additional set and all. I just wanted a very optimal solution without increasing the time and space complexity, if that's possible.

Answer 1

Keep a running set of numbers you have found.

This will allow you to have a one-pass solution.

Start with an empty running set, and iterate through your set of numbers. For each element you iterate through, if its sum-compliment is in the set, remove it from the iterator. Otherwise, add it to the running set.

HashSet<Integer> hs = new HashSet(arr);
HashSet<Integer> running = new HashSet();
int sum = 6;
Iterator<Integer> iter = hs.iterator();
while (iter.hasNext()) {
    int num = iter.next();
    if (running.contains(sum - num)) {
        iter.remove();
    } else {
        running.add(num);
    }
}

This code will modify the original HashSet, and both HashSets will contain the same contents at the end of the code block. In this case, it might be better just to use the running set at the end of the code and not modify the original. That will make this code far more flexible and reusable.

Answer 2

you can use a sorted list instead. first your sort the numbers in increasing order. then you put 2 iterator one in first element and other in last element. then in each step if the sum of 2 items under iterators are smaller than your desired number you should increase first iterator if its grater you should decrease second iterator and if it's equal to what you want you pick them and increase first and decrease second iterator.

it works faster than the set!