Suche nach der Ganzzahl N, die zu ihrer (dezimalen) Umkehrung addiert wird. M

Question

Sei N eine ganze Zahl. Wenn N = 2536 ist, ist das umgekehrte N 6352. Wenn N = 1000000 ist, ist das umgekehrte N 1.
Wir erhalten eine ganze Zahl M, wobei 1 < = M < = 10^(100000).
Wir müssen herausfinden, ob eine ganze Zahl N existiert, wobei N + umgekehrt (N) = M ist.

Irgendwelche Ideen, außer roher Gewalt?

Answer 1

Hier werde ich kurz einen Algorithmus beschreiben. Es sollte beachtet werden, dass viele Details ausgefüllt werden mussten.

Die Grundidee besteht darin, die erste und letzte Ziffer von M zu betrachten, um die Summe der ersten und letzten Ziffer von N zu bestimmen, und dann diese Menge subtrahieren M auf den Fall einer kürzeren Anzahl zu reduzieren.

Rufen wir eine Nummer gut, wenn es als N + reverse(N) geschrieben werden kann.

(EDIT: bei der Umsetzung, wird man brauchen wahrscheinlich eine Funktion IsGood(M, k) die beurteilt, ob M kann für einige N < 10^k als N + reverse(N) geschrieben Aber lassen Sie uns dieses Detail für den Moment überspringen..)

Der Algorithmus, ob eine für die Bestimmung gegebene Anzahl M gut geht wie folgt:

lassen c und d die erste und die letzte Ziffer der M, und sei R der mittlere Teil sein. Das heißt, M hat einen digitalen Ausdruck cRd.

Es gibt zwei Fälle:

• c nicht gleich 1
• c gleich 1

---

In dem Fall, wo c nicht gleich 1 ist, der Ziffer c kann kein Carry sein. Dies ist der Normalfall. Schauen Sie sich jetzt d an.

Wenn d gleich c ist, dann M ist gut, wenn und nur wenn R ist gut.

Wenn d gleich c - 1 ist, dann gibt es einen Übertrag R-c, so M ist gut, wenn und nur wenn 1R im Tragetasche gut (siehe unten).

Wenn d gleich allem anderen ist, dann ist M nicht gut.

---

In dem Fall, wo c-1 gleich ist, gibt es die zusätzliche Möglichkeit, dass c ein Übertrag ist.

Lassen Sie e die erste Ziffer von R sein, und schreiben Sie M als 1eTd.

Wenn d = 9 oder e < d, dann ist die Tragetasche nicht möglich.

(EDIT: Das ist falsch, der Fall d = 9 ist möglich, wenn e = 0.)

Andernfalls wird der Transportkoffer möglich ist, wenn und nur wenn (e - d)(T - 1) gut ist.

Wenn entweder die Tragetasche gehalten wird oder der Normalfall gehalten wird, ist M gut.

---

Beispiel:

uns mit M = 12001 starten lassen.

Seit c = 1 gibt es den Normalfall und den Tragekoffer.

Im Normalfall haben wir d = 1, also müssen wir testen, ob 200 gut ist. Für M = 200, haben wir c = 2 und d = 0, so die Nummer 200 ist nicht gut, daher der Normalfall für M = 12001 schlägt fehl.

Im Tragekoffer müssen wir testen, ob (12001 - 11000 - 11)/10 = 99 gut ist. Für M = 99, haben wir c = 9 und d = 9, so dass dies wieder reduziert, ob 0 ist gut, was offensichtlich wahr ist. Daher gilt der Tragefall. Die Schlussfolgerung ist dann M ist gut.

---

Zeitkomplexität:

Bei einigen detaillierten Argumenten (die ich will nicht hier präsentieren), kann bewiesen werden, dass der Algorithmus in O(log_10(M)) Zeit abläuft.