AddReverse

TCO 22 Semi 1 · 2022-11-17 · by misof

TCO 22 Semi 1 · 2022-11-17 · by misof · Greedy, Simple Math

Show categories

Class Name: AddReverse

Return Type: String

Method Name: solve

Arg Types: (string)

Problem Statement

The reverse of a positive integer X, denoted rev(X), is the number formed by the same digits but in the opposite order.

If a number with trailing zeros is reversed, the trailing zeros become leading zeros and thus they are discarded. For example, rev(4700) = 0074 = 74.

Adding leading zeros before making the reversal is not allowed, so the value rev(X) is always unique.

The String N contains the canonical base-10 representation of a positive integer. Let int(N) denote that integer.

Determine whether there is a positive integer X such that int(N) = X + rev(X). If yes, return a String containing the canonical representation of any one such X. If no, return an empty String instead.

Notes

"Canonical representation" means that there are no leading zeros.

Constraints

N will contain between 1 and 5,000 characters, inclusive.
Each character of N will be a digit ('0'-'9').
The first character of N will not be '0'.

Examples

"88"
Returns: "44"

If we take X = 44, we have rev(X) = 44, and 44 + 44 = 88. Several other correct X exist.

"11"
Returns: "10"

There is only one way to get the sum 11: we need to choose X = 10 and then we add rev(X) = 01 = 1. Thus, "10" is the only correct return value.

"121"
Returns: "110"

Here, X can be any one of the following values: { 29, 38, 47, 56, 65, 74, 83, 92, 110 }. For example, 47 + rev(47) = 47 + 74 = 121, and 110 + rev(110) = 110 + 11 = 121.

"1000"
Returns: ""

There is no X such that X + rev(X) = 1000.

"8617689781716627974239799953268558104995368133253964803950367551453872774660542170889321633224760986746594324716180105428085449517721649499283529526364681169662473935317004154706903574151168106089617134726487657709817483650479559786844269273923023840134724422157707120274565915612535909461301177839153346029486261594412517774583702702210196951976780511104850143911897201017231876975274443398423366229799253907327472468390067077217708890226695869669260219915374835300056669684863982917134013924796488434487855997447918515006781120568279058327934147865603682914825214497652841312968462167944367126084206842976762205941230123840032948703000068283200039762973798366318302361896944107623179898637480696580759386973665789648614650471283489639476614570865146914157519919376381648440384967751166873840899900275372263329748667985112909205300076422016017817817790912725210058673580685259785646590064734779747010587926211675664634571477675345313750650758249376306326728461388205612201352940176284682231423728780912139667931846407253953541223218621486329066534435827186857452635977667471093657567477846883001842197148172324909848004773619783994123807206336422216591264773399062990594143930265682898525718410074549445755547662673282754502985891789946864059520650789777796060111683211663952989715441516060610850118771008085218930639135960541389598912449071082008415226489155647799247938845843800679249081869422896200591145686407804197072414713411769019970131613011689954336203202640605196196051526663737327621053154659057419501706847175047851174943308694242436690394500008582189160222052517437878395557785970034588071369124600121018757953881773542781429055665039475054259641271142366940791701010619336224664001578781091105011893964820888371739215881205949912528625424043111398203240180057817663516375600189218868017451129553513970986985850130944072330324777026705374552114503345092783256349911497825615986279042284123142445018948375496288150183379001444935072192462741663622774365666564303033491344322720789730365042988364459620181912029759616812292439998364067969559411264775188583855533231331502046557537466095168749350746704184982491426698044714554179806128490468547471637310515898232649699762770066756317872797730695444640805927009360301676307405731070495674977132452495541165382532540163845732824051504674810658265491259420022129461079767619783574361711465457789179009960488960039428148854317888861066761956668787032802769792827094889385309544154362178136089917202732596775953038353068705409653444555532669036068603637413485777062362117189916317722623614548144838894917172979673073406778667690576711578888234479508339400588950590098719877545750082534752979167580800648322200140620856617670183675040613183366583610342451945611444952552306804665950710276137135761030648996296081355435971278961788236467699673669969472228986151028460747547749948306079823455165508856350842904823976479440567625905647456557502051331313355493758815774631149550687714528999451932087158579312091820159643747803395730269980272233341953293133566566723772372670472731912815295440999822920507935954638499205432513203931409716896156277942289526523782904434154112454635087197874230232704590309485907790704054549311547097689218820956836153558177610810323919041102414156158263089505921796119371737891274683982205010910778861003673236329260101070881386742410731458525605738405665509340773552681783607479201111054308740707865299705778644938798337251403221608822759099944940867342433869123484820497404826387171049236609653612600367336283567252505826914170462013115345489961203061320689208682034175141707014078036866510861015993248591809518869974575479387528977466608857225138101712698443189058842449596409460299124808101669209491060606152336268902493672122871109605977878980461248613587489881885902944582832672567456565549553710138166248992864729293514059902608943685620857222137426017084313904869163674117390095231718516912581002786497747747662911736667806263437586916395344246609336842268013321543583636937471397670402190779263252321873835720393531022165017930659177226125839418580471474124534876750664265665662216287960107468775374609955475879614860864658610124183190867197088196192346700034920093114797668480332631744630989990482786622576604840447371736839289148604186416680665165749359952830651464168459876653796938580756970847358989813258114386991533128126638973802579410022828700002968503300472221321484132566803377123806317623508611647703131383458044225174202774054688514287239609728650111777095148198437995587855337856874293204407182903594868666510926473746089230618670675967319889167227697699948532748327093528979325634238933445824706692317201016992193409495010060777792487020122071963963678252044862516949305443410377820931550095362056186644830216967611245374310384203183828635376879559849474738180077576757264406169906107622514653996964613117035294842669610765627349342928950561178049555798345009816175125055585800574323362228989721360574683684541546739493094603423428634895117459722499980324697366270779867267"
Returns: "7817689775865827967179799946688549554987689633247957803949766775777786767655536669988666572624755978945894267665679597767997749459665879498682768766284675589886793928258503654698897487576167555589616573868478849659767397649779559786777268673866967779567864421657698569674485865556828859456295677779076738968786186587356767767883696896659696876896775505597849576956896695966666868967694443398363365629798647856667472389789986988666858889666695789668689619858373975295056668877857982866573513924788487767487855997377918464956776069789689988327867577864897676914767663797576775656967756589943688565577656776976686604975665122979966948696999987676699539756973798366267652356896877557562679898576775696575758786973585789577807575465676789578768857565785146863587468968776376639779777958876166872935899895267766656669748667977556859197699988761965967809817699956717659558587580684688978645889557674778878959887865661668584627565768874744657675645758178775655668669460787697856695676879668677876666423668775861579667931776398653882770623159866395729066467767926686857376568977666785586886786769846876995971688577666667859839504767568897987563807155676366666585687767398556989893643929664876898465667759567778745685547656666676754496985886789876857558765579988977795559555876656663946988865376465555555849568685957577659869878575959776388898862448986076957757668488585647798647878774973799878678576859766895695585575686357753696566757663356768519889626556960889877335652696879804688188976466657728666820552653888556768795856838674539845674872658687636376685394499958576188585162046766769878394787778969967587565768563895065968749953876766772775768548584538787984258875665576766875785895959868668617857995878775585597961893883965887766678658876198949856528568417042555798197179599557767586758695595188668867958775568777457965898985849569973566269667896968705367476557753344586777185678961497765565986198536683566571777968948367788687579682698995777867572191781935856822773685658557652966786337666869989669684976979763759569676856529758858756686739998287567889488706264775188577848472665665796976556837465588167879349938697677982485726599974664547679755567789767776765877255465898226649699682769986678667871899665695374575755926999755250868656755725565495667976566746494775587781832479586975672817550797667959857688485689369966628755999759568982867286705765457789178959889788889978767578777667888785566755986668778972752769792768587888777708773653686669568589866651866896775876537753068655358852774500760080500500000060056700000075680550500057658055760050770067060007058500000000500608000000795000055700000566700750660600700070700500000000000075005707070080508000805070055500500755007750080586007070056000600786750600070067755670006075650007000005055000560567080505069000000505600700005608980000567700800000800000006000000505500675070770070070650500056000500708900075000007056008080000780007050000070000705075665650607006000000000005070700800056700000075065508570000055505050500070068006600860600080585566005076600566008000860000086085080860000057607665000860050750067077000000507660756550065050800000500600000590760706006050000576555707000008500886560606050790650000008805006506770655768500000550005000867576700500050850606000065550007007500006500007005007550605060005580800000507055055000075006086067660570505085005600065655065670000707860050807050665000776005000008000505505070650065050007600007000770000008660575000605750006000500000005000606066000560700055008050058000585070560050770050050080668006000605707008050080675050550007700080506505050800050005500507565050050500500000755005050006569005050750080000780700600060000000750008557560505005800000500070005670000650670609557050505800550005505050505600580006000005556085550050000080080705570056000700005000006000006066006000000700070776050560500600006080060000050070006050006007755000555500660500000656006880506000058000507565050758050785006000008070870776055860000007606700000050097666600000060905578500060770700068000700000000650505000600005655086067050606765055577050060009508560560060700005005706560060088075007000807000550600070508680000607050070007080750000006800050557006590900008000500500667800067000506557000000000666065067005000005090000005788007060668005000060590500750500000805007577070600076065005707080700000800000060005000005070600000050600556600005000560500000000006000050056060800006000006600680005655690065700006600556050658760008755070006565606700070557500006006070000756600000709858770505000500500000700000000007660008000000050650500006007080000005000680007500060750000800000650000580558800800068700000660506060000060000600000000857008005650505050005596650007055005000805700050555085000076000575507005700070607066700600055005000507075500500800060558000050000686650606506500060007600000000070006800500508088008580650000050550005756806008000050058507000865779755000800670670060000775508500077800667050050507500070087005000060605560090055005007006806765770060000007006000058767000558000856000000607000080585000000080"

Submissions are judged against all 126 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AddReverse with a public method string solve(string N) · 126 test cases · 2 s / 256 MB per case