Помните Савву Лебедева? Ранее он делился с нами подборками бесплатных ресурсов по C++. А теперь он принес нам еще одну интересную задачу для этого языка программирования. Время размять наши серые клеточки:

Дан непустой массив целочисленных элементов, где каждый элемент повторяется дважды, кроме одного.
Найдите этот одинокий элемент.
Идеально выполнить за линейную сложность по времени и константную сложность по памяти.

Пример 1:
Ввод: nums = [2,2,1]
Вывод: 1

Пример 2:
Ввод: nums = [4,1,2,1,2]
Вывод: 4

Пример 3:
Ввод: nums = [1]
Вывод: 1

Ограничения:
• 1 <= nums.size() <= 3 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Каждый элемент в массиве повторяется дважды, кроме одного: он будет единожды.

int FindSingleNumber(vector<int>& nums) { 
    ...
}

Возвращаемся с оптимальным решением задачи из предыдущего поста от Саввы:

    int FindSingleNumber(const vector<int>& nums) {
        int result = 0;

        for (int n : nums) {
            result ^= n;
        }

        return result;
    }

Такой способ позволяет решить за O(n) по времени и O(1) по памяти.
Это возможно с помощью оператора XOR — исключающее ИЛИ.
Числа состоят из байтов, а байты из битов. XOR работает с битами двух чисел и возвращает в результате третье число. Операция производится поразрядно по одному биту из каждого числа.

XOR вернёт 1, если только один бит равен 1. Получится вот так:

A B C
0 0 0
1 0 1
0 1 1
1 1 0

На примере вот такого вектора: {12, 11, 12} рассмотрим что будет происходить. Покажем только 4 первых бита:

Изначально result равен нулю, значит:
0 ^ 12 — 0000 ^ 1100 = 1100
1100 ^ 11 — 1100 ^ 1011 = 0111
0111 ^ 12 — 0111 ^ 1100 = 1011

В конце получился 1011, это 11 в двоичной системе исчисления.
Первое число просто присвоилось переменной result, а далее биты другого числа вычитались из него. После второго числа в переменной было число 0111 — число 7. Если бы не условие, что все числа будут повторяться дважды, кроме одного, то наличие числа 7 в векторе всё бы испортило и превратило число назад в 0. Второе повторение того же числа (необязательно даже последовательное) отменяет первую операцию. А так как одно число повторяется только один раз, то его никто не компенсировал, и оно осталось храниться в результате.

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

Ответы на вопросы от эксперта.

Савва предлагает ответить на ваши вопросы по C++.

Напоминаем, что Савва не только программист с семилетним стажем, но также наставник и менеджер команды наставников на курсе «Разработчик C++».

Вы можете задать свои вопросы в комментариях под этим постом, а на следующей неделе Савва ответит на них.

Новая задача! На этот раз про Python от Кирилла Быкова, программиста с 18-летним стажем, наставника на курсе «Python-разработчик».

Дана отсортированная последовательность целых чисел и число k. Необходимо найти в этой последовательности число, максимально приближённое к k и вернуть его индекс.

Размер последовательности: 1 <= N <= 10^6
Число k: 0 <= k <= N
Индекс элемента: 0 <= index < N

Примеры

[1, 3, 4, 7, 9, 12] k = 5
Ответ: 2 (число 4)

[1, 3, 4, 12, 15, 15, 18] k = 14
Ответ: 4 (первое число 15)

Решение не должно превышать по временно́й асимптотике O(log(N)), где N — длина массива.

А вот и решение задачи от Кирилла

from bisect import bisect_left

def find(a: [int], k: int) -> int:
    if not a:
        return -1
    i = bisect_left(a, k)
    if i >= len(a):
        return len(a) - 1
    if not i or abs(k-a[i]) <= abs(k-a[i-1]):
        return i
    return i-1

Если задача показалась вам слишком легкой, Кирилл предлагает попробовать выполнить ее без модуля bisect.