Why does my Java code behave differently inside a loop when checking conditions using a HashSet?

Question

I am trying to solve a coding problem where I need to repeatedly double a number (original) as long as it exists in an integer array. To make the lookup faster, I am inserting all elements of the array into a HashSet. My understanding is that this should allow constant-time contains() checks.

However, when I put the doubling condition inside the loop that builds the set, my code fails on certain inputs. Here is the code:

public int findFinalValue(int[] nums, int original) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
        if (set.contains(original)) {
            original *= 2;
        }
    }
    return original;
}

For example, with nums = [5,3,6,1,12] and original = 3, this code returns 12, but the correct result should be 24 because 3 → 6 → 12 → 24 (all appear in the array).

When I move the condition outside the loop like this:

while (set.contains(original)) {
    original *= 2;
}

…it works correctly.

My question is:

Why does checking contains(original) inside the same loop where the set is being built cause incorrect behavior?
I assumed adding elements one by one and checking in the same pass should logically work, since ultimately the same set gets built.

Is there some detail about iteration order, timing of updates, or HashSet behavior that I am misunderstanding?

Any explanation about why the logic only works after the full set is constructed would be greatly appreciated.

I can't reproduce that behavior with your input - see programiz.com/online-compiler/4Gw0KLm0LNDUA for example. It's really important that people can reproduce the results you're seeing. The answer from teapot418 is absolutely right, but doesn't explain the result you're supposedly seeing for [5,3,6,1,12]. — Jon Skeet
– Jon Skeet, Commented Nov 25 at 16:55
Regardless, I think there might be a flaw in checking for membership in a partial set. What happens with an array like [12,5,3,6,1] when original is 3? I think you have to build the entire set first. — VGR
– VGR, Commented Nov 25 at 18:13
Why not take the two subtasks apart? First add all the numbers. Then start checking if original is in the set and double it as long as it is. Would seem simpler to argue about to me. — Anonymous
– Anonymous, Commented Nov 26 at 6:41
Your assumption is wrong. It doesn't make any difference if ultimately the same set gets built, if you are using the partial set before it is properly built. — David Conrad
– David Conrad, Commented Nov 26 at 17:25

teapot418 · Accepted Answer · 2025-11-25 17:03:07Z

3

The argument does not quite work for your values. If you are sure about those, try preparing a minimal reproducible example.

But let's assume nums = [5,3,1,12,6] instead. When adding 6, the current value will be checked against 6 once and doubled to 12. 12 will not be checked against the set again and gets returned.

You will do at most one doubling per loop. Adding one value can reveal the need to perform multiple doublings. This can happen too late in the loop to get you the right result in time.

You could fix that by making the inner if to a while as in:

    for (int num : nums) {
        set.add(num);
        while (set.contains(original)) {
            original *= 2;
        }
    }

edited Nov 25 at 17:03

answered Nov 25 at 16:48

teapot418

2,9682 gold badges8 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why does my Java code behave differently inside a loop when checking conditions using a HashSet?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related