c++ - Closest Palindrome Number -

-

i came across 1 of common interview question find closest palindrome number. if input 127 output 131 , if 125 should give 121 output.

i can come logic logic fails on cases 91, 911. in these inputs give 99 , 919 correct output 88 , 909.

algorithm steps are:

  • convert number string.
  • copy first half second half in reverse order
  • convert number , measure abs. difference original number diff1
  • add 1 half string , copy first half second half in reverse order
  • convert number , measure abs. difference original number diff2
  • if diff1 less diff2 return first number else return second number

this interesting problem. want make more brute force use significant digits , put them in least significant digit locations form palindrome. (i'm going refer difference between palindrome , original "distance")

from i'm going can ignore least significant half of numbers because doesn't matter (it matters when determining distance, that's all).

i'm going take abstract number: abcdef. a,b,c,d,e,f random digits. again said d,e,f not needed determining palindrome want mirror first half of digits onto second half. don't want other way around or we'd modifying more significant digits resulting in greater distance original.

so palindrome abccba, you've stated doesn't shortest distance. "solution" still of form xyzzyx if think minimizing "significance" of digits we're modifying mean we'd want modify c (or middle digit).

lets take step , @ why: abccba

  • at first might tempting modify a because it's in least significant position: far right. in order modify least significant need modify significant. a out.
  • the same can said b, c ends being our digit of choice.

okay we've worked out want modify c our potentially closer number need think bounds. abcdef our original number, , if abccba isn't closest palindrome, be? based on our little detour above can find modifying c. there 2 cases, abcdef greater abccba or less abccba.

if abcdef greater abccba lets add 1 c. we'll t = c+1 have number abttba. we'll test make sure abcdef - abccba > abcdef - abttba , if know abttba nearest palindrome. more modifications c take more , more distant.

alternately if abcdef less abccba we'll subtract 1 c. let's v = c-1. have abvvba, above we'll test: abcdef - abccba > abcdef - abvvba , you'll have same solution.

the trick abcdef between abttba , abvvba , other palindrome between numbers abccba. have 3 options solution. , if compare abcdef abccba need check 2.

i don't think hard adapt numbers of size. , in case of odd number of digits you'd have abcba, abvba , abtba , on...

so examples: lets take 911.

  1. ignore last 1 take first half (round up). 91x.
  2. replace x 9. have 919. out mid point.
  3. we know our original 911 less 919 subtract 1 our middle number our second (lower bound) 909.
  4. compare 911 - 919 , 911 - 909
  5. return 1 smallest difference.

so gives constant time algorithm :)

this appears have, thought i'd elaborate shed light on issue seems small programming error on part otherwise.


Comments

Post a Comment

Popular posts from this blog

c# - How Configure Devart dotConnect for SQLite Code First? -

-
can configure following sample code ? when run following code, error : no entity framework provider found ado.net provider invariant name 'devart.data.sqlite' setting in machine.config <system.data> <dbproviderfactories> <add name="dotconnect sqlite" invariant="devart.data.sqlite" description="devart dotconnect sqlite" type="devart.data.sqlite.sqliteproviderfactory, devart.data.sqlite, version=4.6.287.0, culture=neutral, publickeytoken=09af7300eec23701" /> </dbproviderfactories> </system.data> after add below block code in app.config <?xml version="1.0"?> <configuration>   <configsections> <!-- more information on entity framework configuration, visit http://go.microsoft.com/fwlink/?linkid=237468 --> <section name="entityframework" type="system.data.entity.internal.configfile.entityframeworksection, entit...
Read more

java - Copying object fields -

-
what best way of copying classes when need have 2 independent variables? have simple class: public class myclass { boolean = false; string b= "not empty"; } do need make method : assign(myclass data ) { a= data.a; b= data.b; } is there automatic method copy (duplicate) objects in java? do need make method : pretty close. instead of making method, should make constructor. such constructors called copy constructor , , create them this: myclass(myclass data) { = data.a; b = data.b; } and create copy of instance, use constructor this: myclass obj1 = new myclass(); myclass obj2 = new myclass(obj1); copy constructor can tedious : using copy constructor create deep-copy can tedious, when class has mutable fields. in case, assignment create copy of reference, , not object itself. have create copy of fields (if want deep copy). can go recursive. a better way create deep copy serialize , deserialize object. why not use clone()? ...
Read more

c++ - Clear the memory after returning a vector in a function -

-
i have function processes , stores lot of data in , returns results vector of class. amount of data stored in function tremendous , want clear storage memory of function after finished job. necessary (does function automatically clear memory) or should clear memory function? update: vector<customers> process(char* const *filename, vector<int> id) { vector<customers> list_of_customers; (perform actions) return list_of_customers; } variables defined locally within function automatically released @ end of function scope. destructors objects called, should free memory allocated objects (if objects coded correctly). example of such object std::vector . anything you've allocated new must have corresponding delete release storage. try avoid doing own allocation , use raii instead, i.e. containers or smart pointers.
Read more