-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\$
  • 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\$ – Grimmy 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\$ – Grimmy 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.