Это следующие числа:
Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99.
Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999.
И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...

Собственно решение — дерево сравнений. Будет примерно (двоичный логарифм от максимального значения) сравнений в худшем случае.

Это на мой взгляд будет самое быстрое решение.

Самое элегантное — toString[1] in ('3', '6', '9').

Это следующие числа:
Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99.
Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999.
И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...

Собственно решение — дерево сравнений. Будет максимум 5 сравнений.

Это на мой взгляд будет самое быстрое решение.

Самое элегантное — toString[1] in ('3', '6', '9').