Solução por Lúcio Cardoso
Perceba que a situação do problema é equivalente a um grafo, onde cada número é um vértice. Neste grafo, cada número $$X$$ tem uma aresta para dois outros números: $$X+1$$ e o inverso de $$X$$ (número com digítos na ordem contrária na representação decimal).
Assim, o problema se resume em encontrar o menor caminho de um vértice $$A$$ para um vértice $$B$$ em um grafo com arestas simples (sem peso). Podemos resolver isto utilizando uma BFS (busca em profundidade), em $$O(N)$$, onde $$N$$ é o maior número presente no grafo.
Para descobrir o inverso de um certo número, iremos extrair todos os dígitos deste número na base 10. Depois, organizaremos estes dígitos em ordem inversa, multiplicando-os pelas respectivas potências de 10. A complexidade deste processo é $$O(\log_{10} N)$$ (ou seja, a quantidade de dígitos de um número $$N$$ na base 10).
A complexidade final será, portanto, $$O(N \cdot \log_{10} N)$$. Confira o código abaixo para melhor entendimento:
https://gist.github.com/luciocf/c2a4eec004d4c502856d668de429c43c
Deixe um comentário