🧠 Хитрая задача на C++: "Исчезающее число среди строк"

Условие
Дан список строк, представляющих числа от 1 до 100 включительно. Одного числа нет.
Твоя задача — найти, какого именно числа не хватает.
Нельзя использовать сортировку, std::accumulate, std::unordered_map, std::stoi можно.

Пример:
Массив: ["1", "2", "3", ..., "98", "99"] (без "100")
Ответ: 100

Формат:

int findMissingNumber(const std::vector<std::string>& data);

#include <iostream>
#include <vector>
#include <string>

int findMissingNumber(const std::vector<std::string>& data) {
    int xor_full = 0;
    int xor_data = 0;

    for (int i = 1; i <= 100; ++i) {
        xor_full ^= i;
    }

    for (const auto& s : data) {
        xor_data ^= std::stoi(s);
    }

    return xor_full ^ xor_data;
}

int main() {
    std::vector<std::string> data;
    for (int i = 1; i <= 100; ++i) {
        if (i != 57) { // Удалим 57
            data.push_back(std::to_string(i));
        }
    }

    std::cout << "Пропущено: " << findMissingNumber(data) << std::endl;
    return 0;
}

C++ Academy

🧠 Хитрая задача на C++: "Исчезающее число среди строк"

Условие
Дан список строк, представляющих числа от 1 до 100 включительно. Одного числа нет.
Твоя задача — найти, какого именно числа не хватает.
Нельзя использовать сортировку, std::accumulate, std::unordered_map, std::stoi можно.

Пример:
Массив: ["1", "2", "3", ..., "98", "99"] (без "100")
Ответ: 100

Формат:

int findMissingNumber(const std::vector<std::string>& data);

Решение с XOR

#include <iostream>
#include <vector>
#include <string>

int findMissingNumber(const std::vector<std::string>& data) {
    int xor_full = 0;
    int xor_data = 0;

    for (int i = 1; i <= 100; ++i) {
        xor_full ^= i;
    }

    for (const auto& s : data) {
        xor_data ^= std::stoi(s);
    }

    return xor_full ^ xor_data;
}

Пример использования:

int main() {
    std::vector<std::string> data;
    for (int i = 1; i <= 100; ++i) {
        if (i != 57) { // Удалим 57
            data.push_back(std::to_string(i));
        }
    }

    std::cout << "Пропущено: " << findMissingNumber(data) << std::endl;
    return 0;
}

Почему работает:
XOR — идеальное решение, когда нужно найти одну потерянную величину среди уникальных значений.
a ^ a = 0, 0 ^ b = b. Поэтому:
(XOR всех от 1 до 100) ^ (XOR из данных) = отсутствующее число.

@cpluspluc

hottg.com/cpluspluc/1083

3.5K viewsMay 22 at 08:32