Academy
mediumJS ES6+#125

Palíndromos (rearrange to palindrome)

Prompt

Given a positive number, determine if its digits can be rearranged to form a palindrome (reads same forwards and backwards).

Solution

function canFormPalindrome(n) {
  const digits = String(n).split('')
  const count = {}
  for (const d of digits) count[d] = (count[d] || 0) + 1
  const odds = Object.values(count).filter(c => c % 2 !== 0)
  return odds.length <= 1
}
Mentor's take

The trap in this question is doing what it seems to ask. You never generate rearrangements — a k-digit number has up to k! permutations, and checking each is factorially explosive. Instead you use the palindrome counting invariant: a multiset of characters can form a palindrome iff at most one character has an odd count. Even-count characters mirror across the center; the single odd one (if any) sits in the middle. Odd-length palindromes ("121") have exactly one odd count, even-length ones ("1221") have zero — odds.length <= 1 covers both without branching on length.

So the algorithm is: stringify the number, build the by-now-standard frequency map (see #120), count odd values. O(k) time, O(1) space — digits only have 10 possible values, so the map is bounded. Against the naive permutation search, this is the largest complexity gap in this entire set: O(k) vs O(k!). This problem is the lesson that "can it be rearranged into X?" questions are almost always invariant questions, not search questions — same insight class as anagram grouping and "can you make these strings equal by swaps".

A slicker variant for the follow-up: you don't need counts, only their parity — toggle each digit in a Set (add if absent, delete if present) and check set.size <= 1 at the end. Same complexity, halves the bookkeeping.

Red flag: any attempt to enumerate permutations, even "just a few" — it signals you didn't look for the invariant. Second-tier miss: requiring exactly one odd count, which wrongly rejects even-length palindromes like 1221.

Say it: "I never rearrange anything — a digit multiset forms a palindrome iff at most one digit has an odd count, so it's a frequency map and a parity check: O(k) instead of O(k!)."