Найти а[i+1]—наименьшее число больше a[i], в котором нет цифр из a[i]

Числовая последовательность {an} строится следующим образом: a0 = 1, для любого i ≥ 0 число ai+1, больше ai, равно наименьшему натуральному числу, в десятичном представлении которого нет десятичных цифр ai. По номеру i вывести ai.
Так будет выглядеть последовательность
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111, 200, 311, 400, 511, 600, 711, 800, 911, 2000, 3111, 4000, 5111, 6000, 7111, 8000, 9111, 20000, 31111, 40000, 51111, 60000, 71111, 80000, 91111, 200000...
Как реализовать это? Или хотя бы основной принцип подскажите мучаюсь уже 3 дня, а сдавать завтра

Ответ

Напишите метод, который вернет следующий элемент последовательности по предыдущему:
static int Next(int current) { // Запоминаем все цифры, которые есть в текущем числе var digits = current.ToString().Distinct().ToList(); // Увеличиваем число на 1 до тех пор, пока в новом числе встречаются цифры из входного while ((++current).ToString().Distinct().Intersect(digits).Any()); // Пересечений по цифрам нет, возвращаем результат return current; }
Остается только вызвать его нужное количество раз:
int n = 20; int a = 1; for (int i = 1; i <= n; ++i) a = Next(a); Console.WriteLine(a);

Если требуется вычислять a для больших индексов, то можно придумать решение O(1) (верно?). Как заметил в комментариях @AnT, в последовательности есть "стабильные" участки, можно этим воспользоваться так:
static string GetA(int index) { if (index <= 9) return (index + 1).ToString(); if (index == 10) return "22"; if (index <= 17) return (index - 8).ToString() + ((index - 1) % 2).ToString(); if (index == 18) return "111"; return ((index - 3) % 8 + 2).ToString() + new string((char)((index - 1) % 2 + '0'), (index - 3) / 8); }
Например, GetA(4321) вычисляется мгновенно и возвращает:
800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000