Find the Repeating and the Missing Number

Title: Find the Repeating and the Missing Number

The repeating-and-missing problem is a favorite array question in Java interviews because it forces you to reason about two broken invariants at once. You are given an array that should contain every integer from 1 to N exactly once, but one value has been duplicated and another value is missing entirely. In this guide, you’ll learn a clean counting-based approach, see the full Java program, trace it on a concrete input, and work through the edge cases and follow-up questions interviewers like to ask.

By the end of this tutorial, you’ll understand why a frequency array makes both numbers fall out of a single pass, how the approach generalizes, and when an arithmetic trick can replace the extra memory it uses.

Understanding the Problem

You are given an array numbers of size N whose values are supposed to be the integers 1 through N, each appearing exactly once. Because of a data error, one value appears twice and a different value is missing, so the array still has N elements overall.

For example, if the input is:

int[] numbers = {4, 3, 6, 2, 1, 1};

Then 1 is the repeating number and 5 is the missing number, because 1 appears twice and 5 never appears among the six slots that should hold 1 through 6.

A brute-force solution would compare every pair of elements, costing O(n^2) time. Sorting first brings that down to O(n log n). The counting approach below solves it in a single linear pass.

Approach: Frequency Counting

Since every valid value is bounded between 1 and N, we can allocate a count array of size N + 1 and use each value as a direct index. Walking the input once lets us spot the repeating number the moment its count reaches 2. A second short pass over count finds the one index that was never touched, which is the missing number.

Here are the steps:

1. Read n = numbers.length and allocate count = new int[n + 1].
2. Iterate over numbers, incrementing count[numbers[i]] on every element.
3. The instant any count[numbers[i]] reaches 2, record numbers[i] as the repeating value.
4. After the first loop, scan indices 1 through n of count.
5. The first index whose count is still 0 is the missing value.
6. Return both values together, for example as a two-element array.

Java Program to Find the Repeating and the Missing Number

Here is the complete, runnable Java program that implements the counting approach:

public class FindRepeatingAndMissingNumber {

    public static int[] findRepeatingAndMissing(int[] numbers) {
        int n = numbers.length;
        int[] count = new int[n + 1];
        int repeating = -1;

        for (int i = 0; i < n; i++) {
            count[numbers[i]]++;
            if (count[numbers[i]] == 2) {
                repeating = numbers[i];
            }
        }

        int missing = -1;
        for (int i = 1; i <= n; i++) {
            if (count[i] == 0) {
                missing = i;
                break;
            }
        }

        return new int[] {repeating, missing};
    }

    public static void main(String[] args) {
        int[] numbers = {4, 3, 6, 2, 1, 1};
        int[] result = findRepeatingAndMissing(numbers);

        System.out.println("Repeating number: " + result[0]);
        System.out.println("Missing number: " + result[1]);
    }
}

Explanation of the Program

• The method findRepeatingAndMissing accepts the array numbers and returns a two-element array holding the repeating value at index 0 and the missing value at index 1.
• The count array is sized n + 1 so that values from 1 to n can be used directly as indices without any offset arithmetic.
• During the first for loop, count[numbers[i]]++ records how many times each value has been seen. The check count[numbers[i]] == 2 fires exactly once, the moment the duplicate shows up.
• The second for loop never touches the original array again; it only inspects count to find the single index that stayed at 0.
• The break statement stops the second loop as soon as missing is found, since there is only ever one missing value to look for.
• The main method builds a sample array, calls findRepeatingAndMissing, and prints both results.

Step-by-Step Trace

Let’s trace the algorithm on the input numbers = [3, 1, 2, 5, 3, 6], where n = 6. We expect 3 to come back as the repeating number and 4 as the missing number. Each row below shows one iteration of the first for loop.

After the loop finishes, the second pass scans count[1] through count[6] and finds count[4] == 0, so missing = 4. The invariant is that at the end of the first loop, count[v] holds exactly how many times value v appeared in numbers, and repeating holds the value whose count first reached 2.

Examples

Let’s look at a few concrete runs to see how the repeating value and the missing value can land at different positions in the range.

Example 1: Repeating Value at the Start

The value 1 occupies two of the five slots, so 2 never gets filled in.

int[] numbers = {1, 1, 3, 4, 5};
int[] result = findRepeatingAndMissing(numbers);
System.out.println("Repeating: " + result[0] + ", Missing: " + result[1]);
// Output: Repeating: 1, Missing: 2

Example 2: Missing Value at the Start

Here 1 is the one that never appears, while 5 fills two slots instead of one.

int[] numbers = {2, 3, 4, 5, 5};
int[] result = findRepeatingAndMissing(numbers);
System.out.println("Repeating: " + result[0] + ", Missing: " + result[1]);
// Output: Repeating: 5, Missing: 1

Example 3: Repeating and Missing in the Middle

Both broken values sit in the interior of the range, which is the most common shape you’ll see in practice.

int[] numbers = {1, 2, 2, 4, 5, 6};
int[] result = findRepeatingAndMissing(numbers);
System.out.println("Repeating: " + result[0] + ", Missing: " + result[1]);
// Output: Repeating: 2, Missing: 3

Common Mistakes to Avoid

This problem looks simple, but a few subtle slips show up again and again. Watch out for these:

• Sizing count as new int[n] – using numbers[i] as an index into an array of size n throws ArrayIndexOutOfBoundsException when a value equals n. Allocate count with size n + 1 so every value from 1 to n has a slot.
• Overwriting repeating on every match – checking count[numbers[i]] >= 2 instead of == 2 reassigns repeating every time the duplicate is seen again later, which is harmless here but signals a misunderstanding of the invariant. Check for exact equality to 2 so the assignment happens only once.
• Scanning for missing starting at index 0 – count[0] is always 0 because no valid value is ever 0, so starting the second loop at i = 0 incorrectly reports 0 as missing. Start the scan at i = 1.
• Assuming the repeating and missing values are adjacent – some learners hardcode logic that expects the two broken values to be close together. They can be anywhere in the range, including at opposite ends, so the scan must check every index independently.
• Forgetting that exactly one value is missing and one is duplicated – if the input can have more than one duplicate or more than one missing value, this single-pass count approach only reports one of each; you would need to collect every index whose count is 0 or 2 instead of stopping at the first match.

Edge Cases to Test

Before you call the solution complete, run it through these inputs. They cover the boundaries interviewers probe for:

• Repeating value equals 1 (the first integer)
• Missing value equals n (the last integer)
• Repeating value equals n and missing value equals 1 at the same time
• Smallest valid input: n = 2 with one value duplicated
• Repeating and missing values adjacent to each other
• Array already sorted versus fully shuffled
• Null array reference
• Array whose length does not match the claimed range of values

Additional Considerations

The counting approach runs in O(n) time because it makes exactly two linear passes, one over numbers and one over count. It uses O(n) auxiliary memory for the count array, which is the trade-off worth remembering.

If an interviewer asks for O(1) extra space, switch to the sum-and-sum-of-squares trick: let x be the repeating value and y be the missing value. The difference between the actual sum and the expected sum n * (n + 1) / 2 equals x - y, and the difference between the actual sum of squares and the expected sum of squares equals x^2 - y^2. Dividing the second difference by the first gives x + y, and from x - y and x + y you can solve for both values directly. Use long accumulators, since the sum of squares grows quickly.

Both techniques assume exactly one repeating value and exactly one missing value within the range 1 to n. If that guarantee does not hold, validate the input before trusting either formula.

Interview Follow-up Questions

Once the base version works, expect an interviewer to push further with questions like these:

• Can you solve it with O(1) extra space? – use the sum and sum-of-squares identities instead of a count array; both sums can be computed in a single pass with long accumulators.
• What if there are two repeating values and two missing values instead of one each? – a single count array still works, but you must collect every index with count 0 or count 2 rather than stopping at the first match, so drop the early break.
• What if the array must remain read-only and cannot be modified? – the counting approach never mutates numbers, so it already satisfies a read-only constraint; only an in-place marking trick, such as negating visited indices, would violate it.
• What if the input arrives as a stream and n is not known in advance? – track a running sum, running sum of squares, and a running count of elements seen; once the stream ends, treat the final count as n and apply the arithmetic approach.
• What if the array is too large to fit in memory? – process it in chunks while maintaining running sum and sum-of-squares accumulators across chunks; since both identities are associative, the final answer does not depend on how the chunks were split.

Conclusion

Finding the repeating and the missing number comes down to tracking how many times each valid value shows up. A frequency array makes both broken values fall out of a single linear pass, and the sum-based identities give you a constant-space alternative when memory is tight. Together they cover the two answers interviewers expect you to know for this problem.

Try extending the program to report multiple repeating or missing values, or rewrite it using the sum-and-sum-of-squares trick to compare the two approaches side by side. Working through both versions will make the trade-off between time, space, and code clarity much more concrete.

You can learn more about array algorithms here: Arrays.