Tarkibga o'tish

Teskari raqamlar

32-bitli ishorali butun son x berilgan. Uning raqamlarini teskari tartibda yozing.

Agar natija [-2^31, 2^31 - 1] oralig'idan tashqari bo'lsa — 0 qaytaring.

Kirish:  123
Chiqish: 321

Kirish:  -123
Chiqish: -321

Kirish:  120
Chiqish: 21   // oxirgi nol tushadi

Kirish:  1534236469
Chiqish: 0   // teskari qilinsa overflow, 0 qaytariladi

Asosiy g'oya: raqamlarni chiqarish va yig'ish

Teskari raqamni qurishning mantiqiy yo'li:

  1. xning oxirgi raqamini olish: x % 10
  2. Shu raqamni natijaga qo'shish: result = result * 10 + oxirgi_raqam
  3. x dan oxirgi raqamni olib tashlash: x = x / 10
  4. x = 0 bo'lgunicha takrorlash

Ishora alohida boshqarilmaydi: % va / operatorlari manfiy sonda ham to'g'ri ishlaydi — natija o'z ishorasini saqlaydi.

Pseudocode

FUNCTION REVERSE(x)
    result = 0

    WHILE x ≠ 0
        digit  = x % 10        // oxirgi raqam
        x      = x / 10        // oxirgi raqamni kesib tashlash

        // Overflow tekshirish (result * 10 + digit)
        IF result > INT_MAX / 10
            RETURN 0
        IF result = INT_MAX / 10 VA digit > 7
            RETURN 0

        IF result < INT_MIN / 10
            RETURN 0
        IF result = INT_MIN / 10 VA digit < -8
            RETURN 0

        result = result * 10 + digit

    RETURN result

INT_MAX = 2 147 483 647, INT_MIN = -2 147 483 648.

Overflow tekshirishi

result * 10 + digit > INT_MAX sharti ekvivalent:

result > (INT_MAX - digit) / 10

Lekin bu musbat holat uchun. Salbiy holat ham alohida tekshirilishi mumkin.

Sodda tekshirish usuli: agar |result| > INT_MAX / 10 bo'lsa, keyingi qadam albatta overflow qiladi (* 10 sababli). Agar |result| = INT_MAX / 10 bo'lsa, faqat qo'shiladigan raqam chegaradan oshsa overflow:

INT_MAX = 2 147 483 647   → oxirgi raqam 7
INT_MIN = -2 147 483 648  → oxirgi raqam 8 (salbiy)

Musbat holat:
  result > 214748364 → overflow
  result = 214748364 va digit > 7 → overflow

Salbiy holat:
  result < -214748364 → overflow
  result = -214748364 va digit < -8 → overflow

Bosqichma-bosqich dry run

x = 1234:

Boshlang'ich: result = 0

Qadam 1: digit = 1234 % 10 = 4,  x = 123,  result = 0*10+4  = 4
Qadam 2: digit = 123 % 10  = 3,  x = 12,   result = 4*10+3  = 43
Qadam 3: digit = 12 % 10   = 2,  x = 1,    result = 43*10+2 = 432
Qadam 4: digit = 1 % 10    = 1,  x = 0,    result = 432*10+1 = 4321

x = 0 → WHILE tugaydi
RETURN 4321

x = -120:

Boshlang'ich: result = 0

Qadam 1: digit = -120 % 10 = 0,  x = -12,  result = 0*10+0  = 0
Qadam 2: digit = -12 % 10  = -2, x = -1,   result = 0*10+(-2) = -2
Qadam 3: digit = -1 % 10   = -1, x = 0,    result = -2*10+(-1) = -21

RETURN -21

x = 1000000009 (overflow):

x = 1000000009 → teskari: 9000000001 > INT_MAX

Qadam n: result = 900000000, digit = 9
  result > INT_MAX / 10?  → 900000000 > 214748364 → HA
  RETURN 0

Vaqt va xotira murakkabligi

Xususiyat Qiymat Izoh
Vaqt O(log₁₀ x) Raqamlar soni: log₁₀ x
Xotira O(1) Bir nechta o'zgaruvchi

32-bitli sonda raqamlar soni ko'pi bilan 10 — O(1) ham deyish mumkin.

Edge case'lar

x = 0: 0 % 10 = 0, 0 / 10 = 0, tsikl boshlanmaydi. result = 0.

Oxirgi nollar: 120 → 0 oldinchi qadam, keyingi result = 2, keyin 21. Nol tushadi.

Manfiy son: % operatori belgini saqlaydi, shuning uchun alohida ishlov kerak emas.

Bitta raqamli son: -9 to 9 — teskari o'zi bo'ladi, overflow yo'q.

Chegaradagi son: INT_MAX = 2147483647, teskari 7463847412 — bu INT_MAX dan katta, 0 qaytariladi.

Muqobil: stringga o'tkazish

Ko'p tillarda sonni stringga aylantirish, teskari qilish, keyin songa qayta aylantirish mumkin. Bu kod soddaroq, lekin qo'shimcha xotira va string operatsiyalari kerak.

FUNCTION REVERSE_VIA_STRING(x)
    s      = TO_STRING(ABS(x))
    s      = TESKARI(s)
    result = TO_INT(s)
    IF x < 0
        result = -result
    IF result < INT_MIN YOKI result > INT_MAX
        RETURN 0
    RETURN result

Overflow tekshiruvi katta tipda bajarilishi kerak (masalan, 64-bit), aks holda TO_INT o'zi overflow qilishi mumkin.

Xulosa

Teskari raqamlar — oxirgi raqamni chiqarib natijaga qo'shish tsikli. x % 10 oxirgi raqam, x / 10 uni kesib tashlaydi. Ishora operatsiyalar bilan avtomatik saqlanadi.

Overflow tekshirishi — result * 10 + digit bajarilishidan oldin result > INT_MAX / 10 shartidir. 32-bitli sonda raqamlar soni ko'pi bilan 10 — O(1) amalda.