Задача Bitwise AND

В задаче Bitwise AND дано множество чисел \(S = \{1, 2, 3, ..., N\}\), нужно найти два числа \(A\) и \(B\) такие что значение \(A \& B\) (побитовый оператор И) наибольшее, но меньше заданного \(K\). Вывести наибольшее возможное \(A \& B\).

Ограничения:

  • \(2 \leq N \leq 10^3\)
  • \(2 \leq K \leq N\)

Решение

Решение с перебором рабочее, но не проходит по скорости: всего пар \(N * (N - 1)\), сложность получается \(O(n^2)\).

У этой задачи есть решение за константное время. Предположим число \(K\) нечётное. Это значит что в побитовой записи справа у него находится единица:

\(11_{10} = 1011_2\)

Рассмотрим \(K-1\), в двоичной записи все его цифры совпадают с \(K\) кроме последней в которой находится 0:

\(10_{10} = 1010_2\)

Читать далее Задача Bitwise AND

Наибольший общий делитель двух чисел Фибоначчи

Задача

Найти последнюю цифру наибольшего общего делителя двух чисел Фибоначчи.

Решение

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

Воспользуемся свойством чисел Фибоначчи:

Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов.

\(НОД(F_n, F_m) = F_{НОД(n, m)}\)

Учитвая это вычисляем индекс числа Фибоначчи который одновременно является и нужным НОД, а затем находим его последнее число при помощи периода Пизано.

Сложность

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

Код

На вход подаются два индекса чисел Фибоначчи.

Triangle Quest

Разберём две математические задачи с Hackerrank: Triangle Quest и Triangle Quest 2.

Дано число от 1 до 9 и нужно вывести треугольники из чисел заданного вида. Для числа 4 в первой задаче:

а во второй:

Для вывода допустимо использовать только один цикл, процедуру print и математические операции:

Читать далее Triangle Quest

Генерация всех подмножеств с помощью двоичного представления числа

Другой варианта алгоритма генерации всех подмножеств. Сначала пример.

Дано множество из 5 элементов.

Возьмём пятизначное двоичное число и поставим в соответствие каждой цифре этого числа один из элементов исходного множества. Таким способом мы можем задавать подмножества исходного пятиэелементного множества.

Читать далее Генерация всех подмножеств с помощью двоичного представления числа

Алгоритм генерации всех подмножеств

Алгоритм взят из книги Теоретический минимум по Computer Science (Лабиринт, ЛитРес). Алгоритм итеративный и очень простой для понимания.

На изображении пример работы алгоритма для множества [1, 2, 3].

Генерация всех подмножеств

Каждый элемент исходного множества увеличивает результирующее множества в 2 раза. В итоге множество всех подмножеств будет содержать \(2^n\) элементов, где n — количество элементов исходного множества.

Пример на Python:

Оптимизация условий с помощью оператора xor

Вместо

можно записать

Перебор соседних клеток на двухмерном поле

Рассмотрим задачу похожую на игру Сапёр

Дано прямоугольное поле размером n на m. В поле каждая клетка обозначена либо символом точки ('.') точкой либо звёздочки ('*'). Точка означает пустое поле поле, звёздочка мину. Вывести на экран поле такого же размера где вместо точек указанна цифра - количество мин рядом с этой клеткой.

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

Читать далее Перебор соседних клеток на двухмерном поле

Группировка и подсчёт элементов в списке Python

Рассмотрим задачу

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

Для хранения количества букв будем использовать словарь. Рассмотрим самый простой вариант подсчёта. Пройтись по всем буквам, если текущей буквы ещё нет в словаре, то это первое вхождение - устанавливаем кол-во равным одному, если буква уже есть то увеличиваем кол-во на 1.

Читать далее Группировка и подсчёт элементов в списке Python

Поиск периода Пизано

Даны целые числа \(1 \leq n \leq 10^{18}\) и \(2 \leq m \leq 10^5\), необходимо найти остаток от деления n-го числа Фибоначчи на m.

Читать далее Поиск периода Пизано

Особенности операций целочисленного деления и взятия остатка при работе с отрицательными числами

Когда речь идёт о положительных числах то с операциями целочисленного деления и взятия остатка все довольно просто. Результат всегда положителен и удовлетворяет уравнению

\(div\) - целочисленное деление
\(mod\) - остаток от деления
\(r = (r\ div\ d) * d + (r\ mod\ d)\)

Если же делимое или делитель отрицательные то общая формула остается верной, но результаты отдельных операторов уже отличаются в зависимости от языка программирования.

Читать далее Особенности операций целочисленного деления и взятия остатка при работе с отрицательными числами