Single Number

Условие

Дано число, встречающееся в массиве, и все числа в массиве, кроме одного, встречаются ровно дважды. Найдите число, которое встречается только один раз.

Примеры

Input: [2, 2, 1]

Output: 1

Input: [4, 1, 2, 1, 2]

Output: 4

Решение

fun singleNumber(nums: IntArray): Int {
    var result = 0
    
    // Используем операцию XOR для нахождения числа, которое встречается только один раз.
    // XOR (исключающее ИЛИ) с одинаковыми числами приводит к нулю.
    // XOR (исключающее ИЛИ) с нулем оставляет число без изменений.
    nums.forEach { num ->
        result = result xor num
    }
    
    return result
}

Временная сложность

O(n), где n — количество элементов в массиве. Мы проходим по массиву один раз, выполняя операцию XOR.

Пространственная сложность

O(1). Используется фиксированное количество дополнительной памяти для хранения переменной result.