Find the Element that Appears Thrice

Title: Find the Element that Appears Thrice

An array where every value shows up exactly twice except for one value that shows up exactly three times looks, at first glance, like it needs a frequency map. It does not. In this guide, you will learn how a single XOR pass isolates the triple-occurring value, write a complete Java implementation around that trick, trace the algorithm one iteration at a time, and sharpen your intuition with worked examples, common mistakes, and the follow-up questions interviewers like to drill into.

Understanding the Problem

You are given an integer array nums in which every element occurs exactly twice, except for exactly one element that occurs exactly three times. Return that triple-occurring element.

For instance, if nums = {7, 3, 7, 5, 3, 7, 5}, the value 7 appears three times while 3 and 5 each appear twice, so the answer is 7. The array always has an odd length, since one value contributes three copies and every other value contributes two.

The shape of this problem is a close cousin of the classic ‘find the element that appears once’ problem, where every other value appears twice. There, a plain XOR of the whole array works because x ^ x cancels to 0. Here it is worth checking whether that same trick still applies when the special value shows up three times instead of once.

Approach Using a Single XOR Pass

XOR has two properties that make it useful here: x ^ x = 0, and XOR is commutative and associative, so the order of operations does not matter. Every value that occurs exactly twice contributes x ^ x, which is 0, and XOR-ing with 0 leaves the running result unchanged. Only the triple-occurring value t contributes a non-cancelling term: t ^ t ^ t simplifies to (t ^ t) ^ t, which is 0 ^ t, which is just t.

That means XOR-ing every element of the array together, in any order, leaves exactly the triple-occurring value behind. No frequency counting, hashing, or extra memory is needed.

Here are the steps:

1. Initialize result = 0.
2. Iterate every value num in nums.
3. XOR each value into the accumulator with result ^= num.
4. Every value that occurs exactly twice cancels itself out over the course of the loop, since x ^ x = 0.
5. The value that occurs exactly three times leaves exactly one copy of itself behind, since x ^ x ^ x = x.
6. Once the loop finishes, result holds the triple-occurring value. Return it.

Java Program to Find the Element that Appears Thrice

Let us put the approach into a complete, compilable Java program:

public class FindElementAppearingThrice {

    public static int findThrice(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {7, 3, 7, 5, 3, 7, 5};
        int thrice = findThrice(nums);
        System.out.println("Element appearing three times: " + thrice);
    }
}

Explanation of the Program

• The method findThrice accepts an int[] and returns the single int value that occurs exactly three times.
• result starts at 0, the identity value for XOR, so the very first element XORed into it passes through unchanged.
• The for loop visits every element exactly once and folds it into result with result ^= num, regardless of how many times that value has already appeared.
• Because XOR is commutative and associative, the final value of result does not depend on the order the array is visited in, only on how many times each distinct value appears.
• Values appearing exactly twice always cancel to 0 by the time the loop finishes, no matter how far apart their two occurrences are in the array.
• main calls the method on a sample input and prints the single surviving value, the one that appeared three times.

Step-by-Step Trace

Let us walk the XOR accumulation through a small fresh input so the cancellation is easy to follow. Consider nums = {9, 4, 9, 6, 4, 9, 6}, where 9 is the target output; result starts at 0.

At the end of each iteration, result holds the cumulative XOR of every value processed so far. Notice how 9 and 4 each drift through intermediate values across iterations 1 through 6, yet the very last XOR with 6 at iteration 7 brings result back to exactly 9, because every value that appeared an even number of times has fully cancelled by then.

Examples

Let us look at a few runs that stretch different parts of the algorithm.

Example 1: A Negative Number as the Triple-Occurring Value

int[] nums = {-5, 2, -5, 8, 2, -5, 8};
int thrice = findThrice(nums);

System.out.println("Element appearing three times: " + thrice);
// Output: Element appearing three times: -5

-5 appears three times while 2 and 8 each appear twice. XOR operates on the two’s complement bit pattern regardless of sign, so the cancellation works identically for negative values, and the method correctly returns -5.

Example 2: Larger Values With Two Pairs

int[] nums = {12, 34, 56, 12, 34, 12, 56};
int thrice = findThrice(nums);

System.out.println("Element appearing three times: " + thrice);
// Output: Element appearing three times: 12

12 appears three times, while 34 and 56 each appear twice. The larger magnitudes do not change the algorithm at all; XOR works identically regardless of how large the values are, as long as they fit in an int.

Example 3: The Smallest Possible Input

int[] nums = {42, 42, 42};
int thrice = findThrice(nums);

System.out.println("Element appearing three times: " + thrice);
// Output: Element appearing three times: 42

With only three elements, all identical, there are no pairs to cancel at all. result simply becomes 42 ^ 42 ^ 42, which still simplifies to 42, confirming the trick holds even when the array is nothing but the triple-occurring value.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing the triple-occurrence trick:

• Re-initializing result inside the loop – writing int result = 0; inside the for body resets the accumulator on every iteration, so the method only ever reflects the last element visited. Declare result once, outside the loop.
• Using & or | instead of ^ – a stray bitwise-AND or bitwise-OR looks similar on the page but does not cancel repeated values at all; the method would return an unrelated combination of bits instead of the triple-occurring value. Double-check the operator is ^=.
• Assuming the XOR trick only works for ‘appears once’ – learners who have only seen the single-occurrence variant sometimes reach for a frequency map here, assuming three occurrences must behave differently. x ^ x ^ x still equals x, so plain XOR works directly for this variant too.
• Not validating the input guarantee – the algorithm assumes exactly one value appears three times and every other value appears exactly twice. If that guarantee is violated, for example two values each appear an odd number of times, XOR silently returns their combined XOR instead of either value, with no error raised.
• Reaching for a sum-based formula without checking overflow – an alternative approach computes (3 * sum(distinctValues) - sum(nums)) / 2; it is correct in theory but silently overflows int on large arrays unless the sums are accumulated in a long.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Smallest valid array (three identical elements, no pairs at all)
• Triple-occurring value at the very first index
• Triple-occurring value at the very last index
• Negative value as the triple-occurring element
• Zero as the triple-occurring element
• Integer.MIN_VALUE or Integer.MAX_VALUE as the triple-occurring element
• Large array with many pairs and exactly one triple
• Null array reference

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: A single pass over n elements, so the running time is O(n).
2. Space complexity: Only one int accumulator is used, so the extra space is O(1).
3. Why three occurrences still cancel to one: x ^ x ^ x groups as (x ^ x) ^ x, and the first pair always cancels to 0 regardless of how far apart the three occurrences sit in the array.
4. Alternative with a frequency map: Count occurrences in a Map<Integer, Integer> and return the key whose count equals 3. This costs O(n) extra space but it also lets you validate the input guarantee, which the XOR approach cannot do.
5. Alternative with a sum-based formula: Collect the distinct values into a set, compute (3 * sum(distinctValues) - sum(nums)) / 2 using long accumulators to avoid overflow. This works for arrays where the special value could appear any odd number of times relative to others appearing an even number of times.

Interview Follow-up Questions

Once the base version works, an interviewer will usually probe deeper with questions like these:

• What if the special element appears five times instead of three while others still appear twice? – the same XOR pass still works, since any odd number of occurrences leaves exactly one copy behind after every even pair cancels.
• What if you need to verify the input actually satisfies the one-triple-rest-twice guarantee before trusting the result? – fall back to a frequency map, which costs O(n) extra space but lets you assert that exactly one count equals 3 and every other count equals 2.
• What if more than one value appears exactly three times? – a single XOR no longer isolates one answer, since it would XOR all the triple-occurring values together; use a frequency map instead and collect every key whose count is exactly 3.
• What if the input arrives as an unbounded stream and you cannot store it? – maintain a running XOR as elements arrive; the moment the stream ends, the accumulator already holds the answer, using O(1) memory regardless of stream length.
• What if instead every element appears exactly three times except one that appears exactly once, the classic Single Number II setup? – plain XOR no longer works, because triples no longer cancel to zero under XOR alone; count the set bits at each bit position across all numbers modulo 3 to recover the singly-occurring value.

Conclusion

In this guide, we solved the problem of finding the single value in an array that occurs exactly three times while every other value occurs exactly twice. A single XOR pass is enough, because x ^ x cancels every paired value to 0 while x ^ x ^ x leaves the triple-occurring value standing on its own. The result is an O(n) time, O(1) space solution that needs nothing more than one integer accumulator.

Try adapting the code to validate the input guarantee with a frequency map, generalize it to any odd occurrence count, or compare it against the bit-counting trick used when the roles of ‘once’ and ‘three times’ are swapped. Happy coding!

You can learn more about Array techniques: Arrays