-6
\$\begingroup\$

Input

A single integer in your language's preferred format. This format is non-negotiable (no input as strings, arrays of digits, etc.), but standard I/O formats do apply if otherwise it would be impossible in your language.

Output

A truthy or falsely value, depending on whether the given number is palindromic (same forwards and backwards)

Rules

  • Numbers will always be positive, at least two digits long.
  • This is , so lowest O(n) time complexity wins.

Test cases

  • 123454321 - true
  • 296296 - false
  • 296692 - true
  • 5499456 - false
  • 0 - false/error/any value
\$\endgroup\$

closed as unclear what you're asking by xnor, Wheat Wizard, Mr. Xcoder, Nick Kennedy, Rɪᴋᴇʀ Jul 1 at 18:28

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ In your rules you state the input is less than 99999999, but the first test case is larger than this. \$\endgroup\$ – Kevin Cruijssen Jul 1 at 13:22
  • 4
    \$\begingroup\$ You state that the input is a 16-bit integer, but 4 of the 5 test cases don't fit on 16 bits. \$\endgroup\$ – Grimy Jul 1 at 13:26
  • 1
    \$\begingroup\$ Indeed, the upper bound, 99999999, doesn't fit in 16 bits. \$\endgroup\$ – Adám Jul 1 at 13:27
  • 6
    \$\begingroup\$ Also: specifying any upper bound makes the problem trivially O(1). You should either change to fastest-code or remove the upper bound altogether. \$\endgroup\$ – Grimy Jul 1 at 13:33
  • 6
    \$\begingroup\$ @GezaKerecsenyi No you didn't fix the issue of an upper bound making O(1) solutions trivial. \$\endgroup\$ – Adám Jul 1 at 13:50
6
\$\begingroup\$

APL (Dyalog Unicode), O(1)

⊃∘'111111111110… …10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

Anonymous tacit prefix function.

Try it online!

Simply picks the result from a pre-compiled list.

\$\endgroup\$
  • 2
    \$\begingroup\$ Haha, nice. Didn't think about that. Well done! :) \$\endgroup\$ – Kevin Cruijssen Jul 1 at 13:37
  • 1
    \$\begingroup\$ @LuisMendo It works for me in FFQ/W10 but it takes a very long time to render. Let's hope OP doesn't go to 64 bits… \$\endgroup\$ – Adám Jul 1 at 14:13
  • \$\begingroup\$ @Adám Ah, that was the issue here as well. It took about 1 minute (Chrome, W10) \$\endgroup\$ – Luis Mendo Jul 1 at 14:16
3
\$\begingroup\$

Java, complexity: \$O(\lfloor\log_{10}(n) + 1\rfloor)\$

boolean f(int n){
  int reverse = 0;
  //int debugIterations = 0;
  for(int palindrome = n; palindrome != 0; palindrome /= 10){
    //debugIterations++;
    int lastDigit = palindrome % 10;
    reverse = reverse * 10 + lastDigit;
  }
  //System.out.println("Debug iterations: "+debugIterations);
  return n == reverse;
}

Loops once for every digit in the input-number. Pretty straight-forward implementation tbh..

Try it online.

\$\endgroup\$
1
\$\begingroup\$

Java, O(1)

boolean f(int n){
  if (n <= 0 || n >= 16777216) throw new Error(n+" is not a valid input!");
  int reverse = n/10000000%10*1 + n/1000000%10*10 + n/100000%10*100 + n/10000%10*1000 + n/1000%10*10000 + n/100%10*100000 + n/10%10*1000000 + n/1%10*10000000;
  int len = (int) Math.log10(n);
  reverse/= Math.pow(10, 7-len);
  return reverse == n;
}

Try it online!

Kevin Cruijssen's answer, unrolled for 24-bit numbers.

\$\endgroup\$
  • \$\begingroup\$ I can't post answers since this is on hold, so this is my answer: O(1) a=input();print(1 if a[::-1]==a and len(a)>1 else 0) \$\endgroup\$ – A _ Jul 2 at 3:28
0
\$\begingroup\$

APL+WIN, O(1)

Thanks to Adam for suggested changes to my original code and his explanation - see the comments section.

Prompts for input of integer.

 17=+/(⌽17↑n)=¯17↑n←⍕⎕

Try it online!

\$\endgroup\$
  • \$\begingroup\$ This isn't a [code-golf] challenge, it's [fastest-algorithm]. \$\endgroup\$ – Kevin Cruijssen Jul 1 at 16:26
  • \$\begingroup\$ @Kevin Cruijssen OK so how do we decide which algorithm is fastest. If you compare our examples on TIO APL looks faster? \$\endgroup\$ – Graham Jul 1 at 16:32
  • \$\begingroup\$ If you compare the execution-speed it would be a [fastest-code] challenge. ;) I'm not very good at comparing complexity \$O\$ speeds tbh. But as the challenge is currently stated, the complexity is \$O(1)\$ anyway regardless of the implementation. The challenge is kinda pointless imho.. \$\endgroup\$ – Kevin Cruijssen Jul 1 at 16:59
  • \$\begingroup\$ @Kevin Cruijssen OK if the op is not happy with my entry I will delete it. As APL is an interpreted language I have no idea what is going on under the hood so I do not know how it is handling the problem. I think given what you have said I agree it does seem pointless. \$\endgroup\$ – Graham Jul 1 at 17:06
  • \$\begingroup\$ You should be able to guarantee O(1) with 17=+/(⌽17↑n)=¯17↑n←⍕⎕ since it always has to allocate more memory (3 bytes) than initially assigned (1 or 2 bytes), always reverses a length-17 string, always compares 17 character pairs, and always sums 17 Booleans. \$\endgroup\$ – Adám Jul 2 at 8:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.