Ctrl K

Числа-близнецы на два обмена

Сложная
Дан массив положительных целых чисел values. Разрешена операция: взять одно из двух чисел и поменять местами любые две его цифры. После операции у числа могут появиться ведущие нули — они просто отбрасываются (например, из 310 можно получить 013 = 13). Назовём два числа **близнецами**, если их можно сделать равными, выполнив не больше **двух** таких операций (обе к одному числу или по одной к каждому). Посчитайте количество пар индексов i < j, для которых values[i] и values[j] — близнецы.
Пример 1
values=[1234, 2143, 2341] → 2

1234 и 2143 — близнецы: меняем местами 1 и 2, затем 3 и 4. 2143 и 2341 — близнецы: хватает одного обмена 1 и 3. А из 1234 в 2341 за два обмена не попасть — нужно три. Итого 2 пары.

Пример 2
values=[7, 70, 700] → 3

Ведущие нули разрешены: в 70 меняем цифры → 07 = 7, в 700 меняем 7 с последним нулём → 007 = 7 или с первым → 070 = 70. Все 3 пары — близнецы.

Пример 3
values=[45, 54, 45] → 3

Две одинаковые 45 — близнецы без всяких обменов, и каждая из них — близнец 54. Итого 3 пары.

Ограничения
  • 2 ≤ len(values) ≤ 10⁴
  • 1 ≤ values[i] < 10⁷
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиБлизнецы с точностью до обмена СредняяРавные разрезы после одной замены СложнаяИсходный массив по двум сдвигам СложнаяПобедитель с большинством голосов ЛёгкаяБольше трети голосов Средняя
загружаем Python…
Вход
values=[1234, 2143, 2341]
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 130 тестов на сервере, включая скрытые.