MediumCoding

Strictly Palindromic Number

Asked at

Uber

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Restate that bases range from 2 through n minus 2.
02Inspect representation of n in base n minus 2.
03Show it equals 12 for n at least 4.
04Conclude no such n exists and return false.

Reference answer

Do not convert the number into every base. For every integer n >= 4, consider base b = n - 2, which is one of the required bases. In that base, n = 1*b + 2, so its representation is 12. The digits are different, hence 12 is not a palindrome. Therefore no n >= 4 is strictly palindromic under the problem definition, and the implementation simply returns false. This is O(1) time and O(1) space. In an interview, explain the proof before the code; it demonstrates that the apparent base-conversion task has a structural shortcut. If a variant changes the permitted base range, revisit the proof rather than reusing this conclusion blindly.

Then expect these follow-ups

Why is base n minus 2 always allowed?
Tests: proof details
How would a changed base range affect the result?
Tests: assumptions

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question