Leetcode 9. Palindrome Number

x son berilgan, funksiya agar x palindrom bo’lsa true, aks holda false qaytarishi kerak. Palindrom son deb ohiridan boshiga qarab o’qilganda ham bir xil chiqadigan sonlarga aytiladi. Masalan, 121 – palindrom, 123 – palindrom emas. Shuningdek, -121 ham palindrom emas, chunki teskari o’qilganda 121- bo’lib qoladi.

Ishlash tartibi

Eng oson varianti – sonni stringga, so’ngra arrayga o’girish, uni ohiridan boshiga qarab tartiblash (reverse), so’ngra yana string va songa aylantirish. Chiqqan natija x son bilan solishtirilib, teng bo’lsa true qaytariladi.

Ammo ba’zan qo’shimcha shart sifatida, stringga aylantirishdan qaytarilishi mumkin. Bu holda biz reverse sonini sikl ichida topishga harakat qilamiz:

  1. x = 12321, reversed = 0 bo’lsin. Biz dastlab x ning ohirgi sonini olamiz: x % 10. Uni reversed ga qo’shamiz. x ning ohirgi sonini tashlab ketamiz: 1232
  2. x = 1232, reversed = 0. reversed ni 10 ga ko’paytiramiz. x ning ohirgi sonini olib reversed ga qo’shamiz: reversed = reversed * 10 + x % 10. x ning ohirgi sonini tashlab ketamiz: 123
  3. x = 123, reversed = 12. reversed ni 10 ga ko’paytiramiz. x ning ohirgi sonini olib reversed ga qo’shamiz. reversed = 123, x = 12.
  4. reversed qiymati x dan ortib ketdi. Siklni davom ettirishdan ma’no yo’q, uni. to’xtatamiz.
  5. x soni toq raqamli uzunlikdagi son bo’lgani uchun, uning o’rtadagi qismi reversed’ga o’tib ketdi. Biz x va reversed ni solishtirishdan avval reversed ning ohirgi sonini tashlab ketamiz, chunki o’rtadagi son to’g’ri va teskari o’qiganda ham o’rtada qolgan bo’lardi. Shunda reversed = 12, x = 12 ga teng bo’ldi. Natija: x = reversed. Agar x ning raqamlari soni juft bo’lganda qo’shimcha tekshirishning hojati bo’lmasdi.

Yuqoridagi kodni yangi algoritm bo’yicha qaytadan yozib chiqamiz.

Ishlash vaqti O(n / 2) ga teng.