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

Опубликовано: 21 Сентября, 2022

Учитывая массив arr[] , содержащий N целых чисел, задача состоит в том, чтобы найти следующее большее число X , т. е. X >= arr[i] для каждого i в диапазоне [0, N) , такое, что количество уникальных цифр в X равно ровно 2 .

Пример:

Input: arr[] = {123, 234}
Output: 131 242
Explanation: For the given array, 131 is the smallest number greater that 123 having exactly 2 unique digits. Similarly, 242 is the smallest number greater that 234 having exactly 2 unique digits.

Input: arr[] = {35466666}
Output: 35533333

Наивный подход. Данную проблему можно решить, перебирая все целые числа, большие, чем arr[i] для каждого i в диапазоне [0, N), и отслеживая первые целые числа так, чтобы количество уникальных цифр в целом числе было ровно 2.

Временная сложность: O(N * M), где M представляет максимальный элемент в arr[].
Вспомогательное пространство: O (log N)

Эффективный подход. Описанный выше подход можно оптимизировать с помощью битмаскирования. Можно заметить, что все целые числа, имеющие две цифры в заданном диапазоне, можно вычислить, перебирая все возможные пары двух уникальных цифр и генерируя все цифры, которые могут быть образованы из них. Это можно сделать по алгоритму, обсуждаемому в этой статье. После этого можно использовать заданную структуру данных для хранения всех целых чисел, и для каждого значения arr [i] можно найти наименьшее целое число, большее, чем arr[i] , с помощью функции lower_bound с использованием двоичного поиска.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(10 6 + N * log N) = O (N * log N)
Вспомогательное пространство: O(10 6 ) = O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ