Найти дублированный элемент в массиве от 1 до 100

Найти дублированный элемент в массиве

Объяснение задачи

Дан массив с числами от 1 до 100, где ровно один элемент повторяется один раз. Нужно найти это число за O(n) время и O(1) память.

Решение 1: Использование суммы (самое элегантное)

Идея: сумма чисел от 1 до n = n*(n+1)/2. Вычисляем разницу между фактической суммой и математической.

public class DuplicateFinder {
    /**
     * Находит дублированный элемент через сумму
     * Время: O(n), Память: O(1)
     */
    public static int findDuplicate(int[] arr) {
        int n = arr.length - 1; // Количество уникальных чисел
        
        // Математическая сумма от 1 до n
        long expectedSum = (long) n * (n + 1) / 2;
        
        // Фактическая сумма массива
        long actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        
        return (int) (actualSum - expectedSum);
    }
}

Пример работы:

• Массив: [1, 2, 3, 4, 5, 3]
• expectedSum = 5 * 6 / 2 = 15
• actualSum = 1 + 2 + 3 + 4 + 5 + 3 = 18
• Результат: 18 - 15 = 3

Решение 2: XOR подход

Идея: свойство XOR - a ^ a = 0, a ^ 0 = a. Исключающее ИЛИ всех элементов массива с числами от 1 до n.

public class DuplicateFinder {
    /**
     * Находит дублированный элемент через XOR
     * Время: O(n), Память: O(1)
     */
    public static int findDuplicateXOR(int[] arr) {
        int n = arr.length - 1;
        int xorArray = 0;
        int xorExpected = 0;
        
        // XOR всех элементов массива
        for (int num : arr) {
            xorArray ^= num;
        }
        
        // XOR всех чисел от 1 до n
        for (int i = 1; i <= n; i++) {
            xorExpected ^= i;
        }
        
        // Дублированное число остаётся
        return xorArray ^ xorExpected;
    }
}

Пример работы:

• arr = [1, 2, 3, 3]
• xorArray = 1 ^ 2 ^ 3 ^ 3 = 3
• xorExpected = 1 ^ 2 ^ 3 = 0
• Результат: 3 ^ 0 = 3

Решение 3: С использованием HashSet (для сравнения)

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

public class DuplicateFinder {
    /**
     * Находит дублированный элемент через Set
     * Время: O(n), Память: O(n)
     */
    public static int findDuplicateSet(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        
        for (int num : arr) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }
        
        return -1; // Не найдено (не должно быть по условию)
    }
}

Решение 4: Сортировка (простое, но неоптимальное)

import java.util.Arrays;

public class DuplicateFinder {
    /**
     * Находит дублированный элемент через сортировку
     * Время: O(n log n), Память: O(1) если не считать сортировку
     */
    public static int findDuplicateSorted(int[] arr) {
        Arrays.sort(arr);
        
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] == arr[i + 1]) {
                return arr[i];
            }
        }
        
        return -1;
    }
}

Полные тесты

public class DuplicateTest {
    public static void main(String[] args) {
        int[] test1 = {1, 2, 3, 4, 5, 3};
        int[] test2 = {1, 2, 3, 4, 5, 100, 100};
        int[] test3 = {1, 1};
        
        System.out.println("=== Метод суммы ===");
        System.out.println(DuplicateFinder.findDuplicate(test1)); // 3
        System.out.println(DuplicateFinder.findDuplicate(test2)); // 100
        System.out.println(DuplicateFinder.findDuplicate(test3)); // 1
        
        System.out.println("\n=== Метод XOR ===");
        System.out.println(DuplicateFinder.findDuplicateXOR(test1)); // 3
        System.out.println(DuplicateFinder.findDuplicateXOR(test2)); // 100
        System.out.println(DuplicateFinder.findDuplicateXOR(test3)); // 1
        
        System.out.println("\n=== Метод HashSet ===");
        System.out.println(DuplicateFinder.findDuplicateSet(test1)); // 3
        System.out.println(DuplicateFinder.findDuplicateSet(test2)); // 100
        System.out.println(DuplicateFinder.findDuplicateSet(test3)); // 1
    }
}

Edge cases

public class EdgeCaseTests {
    public static void main(String[] args) {
        // Edge case 1: Минимальный массив
        int[] case1 = {1, 1};
        System.out.println(DuplicateFinder.findDuplicate(case1)); // 1
        
        // Edge case 2: Дублируется первый элемент
        int[] case2 = {1, 2, 3, 4, 1};
        System.out.println(DuplicateFinder.findDuplicate(case2)); // 1
        
        // Edge case 3: Дублируется последний элемент
        int[] case3 = {1, 2, 3, 4, 5, 100, 100};
        System.out.println(DuplicateFinder.findDuplicate(case3)); // 100
        
        // Edge case 4: Большие числа
        int[] case4 = {1, 2, 3, 100, 100};
        System.out.println(DuplicateFinder.findDuplicate(case4)); // 100
    }
}

Сравнение подходов

Вывод

На интервью рекомендуется:

1. Начать с метода сумма — это самое элегантное O(n) решение
2. Упомянуть XOR как альтернативу (не боится переполнения для очень больших чисел)
3. Обсудить trade-off с HashSet (время vs память)

Важно: метод суммы может привести к переполнению при очень больших числах, поэтому используйте long для промежуточных вычислений.