Задача проверки последовательности на палиндром решается за O(n/2). Но для этого нужно иметь последовательный доступ к обоим концам последовательности за O(1).
Если такой возможности нет и имеется доступ только к одному из концов последовательности, то придется обойти всю последовательность, а это уже O(n). Один из таких, достаточно оптимальных алгоритмов для цифр целого числа уже представил
WbICHA.
Чтоб решить эту задачу за O(n/2) нужно понять, как получить крайние цифры числа за O(1).
Крайнюю справа цифру можно получить простым остатком от деления на основание системы счисления, то есть, в случае десятичной системы счисления, на 10.
Для получения крайней справа цифры нужно знать ее порядок (считая справа начиная с 0). Это можно сделать взяв целую часть от логарифма по основанию системы счисления (10). На JS такая операция будет выглядеть так:
Math.trunc(Math.log10(num))
Целая часть от деления числа на 10 в степени порядка правой цифры даст саму эту цифру. На JS это выражается так:
Math.trunc(num / 10 ** Math.trunc(Math.log10(num)))
Так же алгоритм требует равномерного перемещения по последовательности от краев к центру.
Для правой цифры опять все просто, можно брать целую часть от деления числа на основание (10).
Для левой нужно умножить ее на основание в степени порядка и вычесть результат из самого числа, то есть:
num - leftDigit * 10 ** Math.trunc(Math.log10(num))
Осталось учесть пограничные условия:
1. Если крайний левый и крайний правый элемент не равны, то последовательность не является палиндромом
2. Последовательность из одного элемента (число из одной цифры) всегда палиндром.
3. При равенстве крайних элементов последовательность будет палиндромом если палиндромом так же является подпоследовательность без этих элементов.
Пункт 3 подразумевает рекурсию, но такая рекурсия легко разворачивается в цикл, что конечно же более оптимально.
По итогу получим такую функцию:
const isPalindrome = num => {
let n = num;
while (n >= 10) {
const order = 10 ** Math.trunc(Math.log10(n));
const leftDigit = Math.trunc(n / order);
const rightDigit = n % 10;
if (leftDigit !== rightDigit) return false;
n -= leftDigit * order;
n /= 10;
n = Math.trunc(n);
}
return true;
};
P.S. варианты с приведением числа к строке, а тем более с последующим разбиением на массив чисел и разворотом его, просто отвратительны.
Приведение числа к строке - это O(n) если не больше, так как в JS тип number - это по сути float64 и алгоритм приведения учитывает, что число может быть с дробной частью.
Разбиение строки на массив символов (split) - O(n) и требует доп памяти под этот массив.
Реверс массива - O(n/2)
Склейка (join) - опять O(n)
Сравнение строк - еще раз O(n)
И хотя суммарная сложность останется O(n), количество проходов по цифрам числа будет в 5 раз больше, хотя даже на строках можно уложится в 1.5 обхода:
const isPalindrome = num => {
const s = String(num);
for (let i = 0; i < s.length / 2; i++) {
if (s[i] !== s[s.length - i - 1]) return false;
}
return true;
};
