Попроще

Честно признаюсь: предыдущая задача – сложная. Решить её без практики строковых/backtrace алгоритмов, и, тем паче, в рамках собеседования, – маловероятно. Рассмотрим задачу попроще, которая пару дней назад была daily challenge. Продублирую условие:

Given two positive integers num1 and num2, find the positive integer x such that:

x has the same number of set bits as num2, and
The value x XOR num1 is minimal.
Note that XOR is the bitwise XOR operation.

Return the integer x. The test cases are generated such that x is uniquely determined.

The number of set bits of an integer is the number of 1's in its binary representation.

И ограничения:

1 <= num1, num2 <= 10^9

Догадываюсь, что с первого взгляда кажется, что написана какая-то ерунда. Действительно: в этой задаче главное – понять условие правильно. По сути нам нужно "создать" новое число и в него поставить столько единичек, сколько их в num2. Это можно сделать многими способами, но у нас есть дополнительное условие: XOR-сумма с num1 должна быть минимальна. Как известно 1 XOR 1 = 0, 0 XOR 0 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, т.е. имеет смысл идти по битам числа num2 слева направо копируя их в результат (не забывая, что вообще говоря num2 может содержать больше битов, чем нам нужно). А если вдруг мы скопировали весь num2, но битов не хватает – не теряемся, просто заполняем пустые разряды res уже теперь справа налево.

Небольшое замечание перед тем, как я покажу код: вообще в C++, конечно, есть побитовые операторы, сдвиги и т.д., и, можно было реализовывать, опираясь только на них, но удобнее использовать bitset. И вторая ремарка: не вчитывайтесь – попытайтесь решить сами.

class Solution {
public:
    constexpr static const int bin_size = 30;
    using bits = bitset<bin_size>;

    int minimizeXor(int num1, int num2) {
        bits b1 = num1;
        bits b2 = num2;
        bits res = 0;

        int count = b2.count();
        auto index = bin_size - 1;

        while (count && index >= 0)
        {
            if (b1[index])
            {
                res.set(index);
                count--;
            }

            index--;
        }

        index = 0;

        while (count)
        {
            if (!res[index])
            {
                res.set(index);
                count--;
            }
            
            index++;
        }

        return res.to_ulong();
    }
};

#today #c_plus_plus #leetcode #algo

Результаты решения

#today #c_plus_plus #leetcode #algo

Daily question

Не совсем понимаю почему, но второй день подряд вижу забавные задачки на XOR на Leetcode: условие в этот раз длинное – предлагаю прочесть его по ссылке самостоятельно.

Если вкратце: дано два, возможно довольно длинных, целочисленных массива, нужно найти XOR всех возможных пар. Т.е. если в первом массиве 10 элементов, во втором 11, то нужно найти XOR 110 пар – что было бы квадратичным (неэффективным) алгоритмом. Советую решить самим прежде чем читать спойлер и код.

Нам понадобится два свойства операции XOR: её коммутативность, и факт, что XOR-сумма любого числа с самим с собой равна нулю при чётном числе элементов и равна самому элементу при нечётном числе элементов. В гигантском XOR всех-всех пар друг с другом каждый элемент первого массива встретится столько раз, сколько элементов во втором массиве, и аналогично для второго массива. Иначе говоря, всё зависит только от чётности длин массива, и в худшем случае мы получим алгоритм линейный от совокупных длин массива, а в лучшем случае и вовсе – O(1).

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2)
    {
        int res = 0;

        if (nums2.size() % 2 == 1)
        {
            for (const auto& x: nums1)
            {
                res ^= x;
            }
        }

        if (nums1.size() % 2 == 1)
        {
            for (const auto& x: nums2)
            {
                res ^= x;
            }
        }

        return res;
    }
};

#today #c_plus_plus #leetcode #algo

Результаты решения

#today #c_plus_plus #leetcode #algo

Daily question, again

На Leetcode похоже ежемесячник смешных задач на XOR. Всё остальное сразу убираю под спойлер.

Итак, сразу понятно, что о каком-либо переборе всех возможных массивов original с пересчётом их deriverd речь идти не может – это было бы экспоненциальное время работы. Вместо этого внимательно посмотрите на Example 1: в расписанных формулах для элементов derived каждое значение original фигурирует ровно дважды – это значит, что XOR-сумма элементов валидного derived, полученного из произвольного original обязана быть равна нулю.

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int res = 0;

        for (const auto& x: derived)
        {
            res ^= x;
        }

        return res == 0;
    }
};

#today #c_plus_plus #leetcode #algo

Хорош ли номер

Эта серия с Leetcode подзатянулась, но это не значит, что я её не продолжу:) Сегодня предлагаю просто почитать задачу уровня Hard, с удивительно низким для меня уровнем Acceptance порядка 20 процентов – решение я опубликую потом.

Сразу скажу: решение довольно простое, укладывающееся в сотню строк; причём достаточно использовать только сравнение символов, итерирование по строке и прочие низкоуровневые штуки, использовать тут regexp – неспортивно.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Хорош ли номер ч. 2

Вернёмся к задаче из поста: решение я всё ещё придержу. Кстати, в данном случае использование конечных автоматов, предложенных тут в комментариях, в принципе оправдано, хотя – в своём решении я не использую их. Если кто-то из подписчиков реши(л|т), используя этот формализм, – предлагаю привести решение в комментариях.

Я же тут, пока что написал регулярное выражение подходящее под условие (\-\+)?((\d)+)|((\d*\.\d+)|(\d+\.\d*))((e|E)\d+)? – считайте это подсказкой.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Хорош ли номер ч. 3

Закончим задачу из поста.

Итак, в прошлый раз я уже писал regexp, теперь проговорю словами: по сути валидное число это decimal или integer, которые могут быть продолжены символом 'e' или 'E' за которым идёт integer. Очень читабельное решение получается при разбиении строки на две части – до и после 'e/E'. Полученные части будут достаточно просты, что б проверить их циклом в один проход.

Код будет в комментарии. Обратите внимание на функцию isDecimal: на самом деле она не отличает decimal от integer, но это работает:) – Да, углы немного срезаны. Итоговая сложность, очевидно, линейна.

#today #c_plus_plus #leetcode #algo

Обычно я пишу заметки в тот момент, когда у меня на руках уже есть готовое решение – возможно, оно сделано несколько лет назад, возможно – сегодня.

Однако, часто так бывает, что найти хорошее решение, не изобретая велосипед, – практически невозможно. Неожиданный пример такой проблемы: умножение двух uint64_t по модулю в C++. Тут важны все слова: умножить без модуля – не очень сложно, использовать uint32_t – легко, не в C++ – окей, кто знает – тот знает.

А в чём собственно проблема? – в том, что, вообще говоря, произведение двух uint64_t не влезет в uint64_t, а стандартного типа uint128_t – нет.

Но есть же какая-то библиотека, где это уже сделано? – конечно, тот же gmp, но это не то решение, которое я ищу.
А что, если разбить uint64_t на две половинки по 32 бита, как-то их перемножить и т.д.? – к сожалению, это тоже не работает, в какой-то момент в формуле всё равно вылезет необходимость перемножить два uint64_t. Есть пара похожих вариантов, которые мне лень расписывать, и которые тоже не работают.
А есть же расширение __int128? – Да, есть, но только для GCC.
И что ничего нельзя сделать, если хочется получить самописную платформонезависимую реализацию данной операции? – Можно, вот только потребует это удивительно много строк кода.

Рассмотрим пару вариантов:
1) реализовать сначала обычное умножение с сохранением в пару uint64_t, потом по-честному поделить на модуль, вернув остаток
2) использовать алгоритм Монтгомери

Относительно первого варианта: реализовать умножение – сравнительно легко, вот с делением будет проблема: стандартный алгоритм (примерно то, что изучается в школе) потребует явный цикл...есть другие алгоритмы, но они ещё более неприятны в имплементации (например, рассмотренный мной метод Ньютона-Рафсона)

Относительно второго варианта – он выходит за рамки среднестатистических знаний об алгоритмах (включая, и мои знания на данный момент), но вот вам ссылка.

Вишенка на этом торте безумной "удобности" C++ является то, что процессор это умеет: можно посмотреть тут. Можно в godbolt дизассемблерить простой листинг для GCC.

typedef unsigned __int128 uint128_t;
uint128_t mult(uint64_t a, uint64_t b)
{
    return uint128_t(a) * uint128_t(b);
}

Так что вы говорите там будет интересного в новом стандарте?

#today #c_plus_plus #algo #hatred

Продолжим то, что начали в прошлый раз.

Несмотря на простую, формулировку testcases пригодятся: язык хоть мне и знакомый, но не родной – редко приходится озвучивать числительные да и ещё такие большие.

Итак, для 1 234 567 нужно выдать "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven". Думаю довольно очевидно, что все уникальные числительные будут константами так или иначе организованными в листинге, а именно это числа 0-19, 20, 30...90, 100, 1000, 1000 000, 1000 000 000. Далее, по большей части я вынужден перефразировать подсказки данные в условии (честно скажу, что я прочёл их уже после успешного submit).

Рассмотрите отдельные тройки разрядов, обратите внимания, что их звучание однотипно – отличие только в том, что одна группа это Million, другая Thousand, ну а последняя (Ones) – суффикса не требует. Так же нам везёт, что все эти Million/Thousand сами не склоняются по числу ( не требует 's'). Внутри же этой тройки разрядов всё достаточно просто: озвучиваем первую значащую цифру, прибавляя Hundred, далее если в оставшихся двух разрядах число старше 19, то озвучиваем сначала десяток, потом вторую цифру, если число не старше 19 – озвучиваем сразу две цифры. И да – нули не озвучиваем.

Как выделяются тройки разрядов и обработку corner-cases – посмотрите в листинге или в подсказках на платформе. Листинг в комментарии к посту.

#leetcode #algo #c_plus_plus #English