Java Programs›Arrays›Find Repeated Number

Find Repeated Number in Java

intermediate· Arrays · Array

Problem

An array of n + 1 integers, each between 1 and n, always has at least one repeated value, since there are only n distinct possibilities for n + 1 slots.

Given an array of n + 1 integers, each between 1 and n, find the one value that repeats.

Input

[4, 3, 1, 5, 2, 3], n = 5

Output

Repeated number: 3

Java Program

Java

public class FindRepeatedNumber {
    public static void main(String[] args) {
        int[] arr = {4, 3, 1, 5, 2, 3};
        int n = 5;

        int expectedSum = n * (n + 1) / 2; // sum if every value 1..n appeared exactly once
        int actualSum = 0;
        for (int num : arr) {
            actualSum += num; // includes one extra copy of the repeated value
        }

        System.out.println("Repeated number: " + (actualSum - expectedSum));
    }
}

▶ Run Code

Output

Repeated number: 3

Core Logic

The array's actual sum is exactly the expected sum of 1 to n plus one extra copy of whichever number repeated — so subtracting the expected sum back out isolates it.

How It Works

1n * (n + 1) / 2 computes the expected sum if every number from 1 to n appeared exactly once.
2A loop adds up every element actually present in arr, which has n + 1 elements — one more than a plain 1-to-n run.
3That extra element is a second copy of the repeated number, so actualSum is exactly expectedSum plus the repeated value.
4actualSum - expectedSum leaves exactly the number that repeated.

For n = 5, the expected sum is 15; the array [4, 3, 1, 5, 2, 3] actually sums to 18, so the repeated number is 18 - 15 = 3.

💡

Key Point: This is the mirror image of finding a missing number — there, the array is one short and the actual sum comes in low; here, the array has one extra and the actual sum comes in high.

Complexity

Time Complexity: O(n)Space Complexity: O(1)

Why: Computing the expected sum is a constant-time formula, and the actual sum only needs a single pass through the array with one running total.

Key Concepts

arithmetic sum formulapigeonhole principle

Approach 2: HashSet Detection

Java

import java.util.HashSet;
import java.util.Set;

public class FindRepeatedNumberSet {
    public static void main(String[] args) {
        int[] arr = {4, 3, 1, 5, 2, 3};
        Set<Integer> seen = new HashSet<>();

        for (int num : arr) {
            if (seen.contains(num)) { // already encountered — this is the repeat
                System.out.println("Repeated number: " + num);
                break; // found the repeat, no need to scan further
            }
            seen.add(num);
        }
    }
}

▶ Run Code

Output

Repeated number: 3

Core Logic

Tracking every number already seen in a set, and stopping the instant a number shows up that's already in it, finds the repeat directly — no arithmetic needed.

How It Works

1A HashSet<Integer> named seen starts empty.
2For each number, seen.contains(num) checks whether it has already been added.
3The first time this check succeeds, that number is the repeat — it's printed immediately and the loop breaks.
4If the check fails, the number is new so far, and seen.add(num) records it before moving on.

Scanning [4, 3, 1, 5, 2, 3], the numbers 4, 3, 1, 5, and 2 are each added as new — then the second 3 is found already in seen, so 3 is reported.

💡

Key Point: Unlike the sum-formula version, this doesn't rely on the array holding exactly the range 1 to n — it works for any array where finding the first repeat is the goal.

Complexity

Time Complexity: O(n)Space Complexity: O(n)

Why: In the worst case the repeat is found last, so the set can grow to hold nearly all n + 1 elements before that happens.

Key Concepts

HashSetcontains()early exit with break

Approach 3: Java 8

Java

import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

public class FindRepeatedNumberStream {
    public static void main(String[] args) {
        int[] arr = {4, 3, 1, 5, 2, 3};

        // Groups by value, counts occurrences, then keeps only the one that occurred more than once
        int repeated = Arrays.stream(arr)
            .boxed()
            .collect(Collectors.groupingBy(n -> n, Collectors.counting()))
            .entrySet()
            .stream()
            .filter(e -> e.getValue() > 1)
            .findFirst()
            .get()
            .getKey();

        System.out.println("Repeated number: " + repeated);
    }
}

▶ Run Code

Output

Repeated number: 3

Core Logic

Grouping every value by identity and counting occurrences, then filtering down to the one whose count exceeds one, finds the repeat declaratively — without either the sum-formula's range assumption or the HashSet's seen-before scan.

How It Works

1Arrays.stream(arr).boxed() turns the array into a Stream<Integer>.
2Collectors.groupingBy(n -> n, Collectors.counting()) builds a Map<Integer, Long> of each value's occurrence count.
3entrySet().stream().filter(e -> e.getValue() > 1) keeps only entries that occurred more than once.
4.findFirst().get().getKey() extracts that entry's key — the repeated number.

Grouping [4, 3, 1, 5, 2, 3] gives counts 4: 1, 3: 2, 1: 1, 5: 1, 2: 1; filtering for a count above 1 leaves only 3.

💡

Key Point: Because the array is guaranteed to have exactly one repeated value, findFirst() is safe here even though a HashMap-backed grouping has no defined iteration order — only one entry ever survives the filter, so which one 'first' refers to doesn't matter.

Complexity

Time Complexity: O(n)Space Complexity: O(n)

Why: groupingBy() visits every element once to build a map holding one entry per distinct value, up to n in the worst case.

Key Concepts

StreamCollectors.groupingBy()Collectors.counting()filter()

← Previous

Find Peak Element in an Array

Find Second Largest Element in an Array

Related Programs

Arraysbeginner

Average Array Elements

Check Array Is Sorted

Arraysbeginner

Compare Two Arrays