005 — Palindrome Number¶

004-এ তুমি সংখ্যা উল্টাতে শিখেছ (rev = rev * 10 + d)। আজকের problem আসলে সেই শেখারই পুরস্কার — palindrome চেক করা মানে শুধু "উল্টে দেখো original-এর সাথে মেলে কিনা"। তাই এটা প্রায় free একটা problem, কিন্তু এর ভেতরে level 0-এর সবচেয়ে কুখ্যাত একটা bug লুকিয়ে আছে (original copy না রাখা) — সেটা একবার চোখে দেখে নিলে সারা জীবন মনে থাকবে।

Source¶

Original source: LeetCode — Palindrome Number — https://leetcode.com/problems/palindrome-number/
Platform: LeetCode — https://leetcode.com/problems/palindrome-number/
Topic: Math-based programming fundamentals → Level 0: Absolute Basics
Difficulty: Easy
Pattern: reverse + compare
Basic idea inherited from: 004 (Reverse Number)

1. Problem in simple words¶

একটা integer n দেওয়া আছে। বলতে হবে এটা palindrome কিনা — মানে উল্টে পড়লেও কি একই সংখ্যা থাকে?

121 উল্টালে 121 → একই → palindrome (True)
1331 উল্টালে 1331 → একই → palindrome (True)
123 উল্টালে 321 → আলাদা → palindrome নয় (False)
7 উল্টালে 7 → এক digit সবসময় palindrome (True)

আর একটা নিয়ম: negative সংখ্যা palindrome নয় — কারণ -121 উল্টালে 121- হয়, যেটা একই নয় (minus চিহ্ন সামনে থাকে, পেছনে নয়)।

2. What is the math idea?¶

কোনো নতুন গণিত নেই — পুরোটাই 004-এর reverse, তার উপর একটা তুলনা। চিন্তা তিন ধাপে:

মূল সংখ্যাটা আলাদা করে মনে রাখো (copy)
সংখ্যাটা উল্টে ফেলো (004-এর rev = rev * 10 + d loop)
উল্টানো সংখ্যা মূল সংখ্যার সমান হলে palindrome, নাহলে নয়

original = n        # মূলটা মনে রাখো (n তো ভেঙে যাবে!)
rev = 0
যতক্ষণ n > 0:
    rev = rev * 10 + n % 10
    n //= 10
return rev == original

3. Which basic idea does this inherit from?¶

সরাসরি 004 (Reverse Number) থেকে — এর reverse loop-টা হুবহু 004-এর।

004 আর 005-এর সম্পর্ক এক বাক্যে:

004:  সংখ্যা উল্টাও -> rev ফেরত দাও
005:  সংখ্যা উল্টাও -> rev == original কিনা ফেরত দাও
                       ^^^^^^^^^^^^^^^^^
                   শুধু শেষে একটা তুলনা বাড়ল

মানে 004 যদি না জানতে, 005 কঠিন লাগত। কিন্তু reverse বানানো শিখে ফেলায় এখানে শুধু একটা == যোগ করতে হলো। এটাই "Inherits from"-এর আসল মানে: আগের problem-টা এখানে উত্তরের অর্ধেক হয়ে বসে আছে।

4. Real-life analogy¶

ভাবো তোমার হাতে একটা পুঁতির মালা, আর তুমি দেখতে চাও মালাটা প্রতিসম (symmetric) কিনা — মানে এক প্রান্ত থেকে পড়লে আর উল্টো প্রান্ত থেকে পড়লে রঙের ক্রম একই কিনা।

তুমি মালাটার একটা হুবহু নকল বানাও, কিন্তু উল্টো দিক থেকে গেঁথে → এটাই reverse বানানো
এবার আসল মালা আর উল্টো মালা পাশাপাশি রেখে মেলাও → এটাই rev == original
দুটো হুবহু এক দেখালে → মালা প্রতিসম → palindrome

খুব জরুরি: নকল বানানোর আগে আসল মালাটা সরিয়ে রাখতে হবে, নাহলে গাঁথতে গাঁথতে আসলটাই খুলে যাবে — মেলাবে কীসের সাথে? এটাই code-এ original = n রাখার কারণ।

5. Visual explanation¶

n = 121 reverse হচ্ছে, পাশে original অপরিবর্তিত বসে আছে — শেষে দুজনে মেলে:

original = 121  (সরিয়ে রাখা, অটুট)

n = 121   rev = 0×10 + 1   = 1      n -> 12
n = 12    rev = 1×10 + 2   = 12     n -> 1
n = 1     rev = 12×10 + 1  = 121    n -> 0   (থামো!)

মেলাও:  rev (121) == original (121)  ->  True  ->  palindrome

আর একটা non-palindrome, যেখানে শেষে তুলনা ফেল করে:

original = 123  (অটুট)

n = 123 -> rev = 3      n = 12 -> rev = 32      n = 1 -> rev = 321

মেলাও:  rev (321) == original (123)  ->  False  ->  palindrome নয়

6. Example input and output¶

input   ->  output   (কীভাবে)
------------------------------
  121   ->  True     (121 উল্টালেও 121)
 1331   ->  True     (1331 উল্টালেও 1331)
  123   ->  False    (321 ≠ 123)
    7   ->  True     (এক digit সবসময় palindrome)
    0   ->  True     (0 উল্টালেও 0)
  -121  ->  False    <-- negative কখনো palindrome নয়
   10   ->  False    (উল্টালে 01 = 1, 10 ≠ 1)

দুটো জিনিস খেয়াল করো: negative সবসময় False, আর 10-এর মতো trailing-zero সংখ্যা False (উল্টালে 1 হয়ে যায়, 10-এর সমান নয়)।

7. Brute force thinking¶

প্রথমে যেটা মাথায় আসে — সংখ্যাটাকে string বানিয়ে তার উল্টোটার সাথে সরাসরি মেলাই:

def is_palindrome_str(n):
    if n < 0:
        return False
    s = str(n)
    return s == s[::-1]   # string আর তার উল্টোটা মেলে কিনা

s[::-1] string-টা উল্টে দেয়, তারপর == দিয়ে মিলিয়ে দেখি। এক লাইন, পড়তে সহজ, ঠিক উত্তর দেয়। তাহলে সমস্যা কোথায়?

8. Why brute force may be slow¶

Time-এর দিক থেকে string version "ধীর" নয় — দুটোই digit সংখ্যার সমান কাজ করে। কিন্তু:

বাড়তি জায়গা: str(n) আর s[::-1] দুটো string বানায় → O(digit) extra space। arithmetic version O(1) space-এ চলে।
ভাষা-নির্ভরতা: Python-এ s[::-1] সহজ, কিন্তু C++/Java-তে এটা ততটা মসৃণ নয়। arithmetic পদ্ধতি যেকোনো ভাষায় একই — interview-তে বড় সুবিধা।
চিন্তার অনুশীলন: এই level-এর লক্ষ্য digit নিয়ে arithmetic-এ স্বচ্ছন্দ হওয়া। reverse loop নিজে লিখতে পারাটাই এখানে শেখার আসল জিনিস।

মূল কথা: string version ঠিক উত্তর দেয়, আর interview-তে বললে দোষ নেই — কিন্তু পাশাপাশি arithmetic version-ও জানা থাকলে তুমি দেখাতে পারো যে reverse loop-টা তোমার আয়ত্তে।

9. Better thinking¶

String বাদ — সরাসরি 004-এর reverse loop চালিয়ে, তারপর মূলের সাথে মেলাই:

def is_palindrome(n):
    if n < 0:
        return False        # negative কখনো palindrome নয়
    original = n            # মূলটা মনে রাখো (n ভেঙে যাবে)
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n //= 10
    return rev == original

কোনো string নেই — শুধু সংখ্যা, একটা reverse loop, আর একটা তুলনা। জায়গা লাগছে O(1)।

10. Thinking tweak¶

আসল মোচড় এক বাক্যে: palindrome চেক করা মানে নতুন কিছু না — শুধু "উল্টে দেখো original-এর সাথে মেলে কিনা"; তাই 004-এর reverse-টা আগে মনে আনো, তারপর একটা == বসাও।

আর সাথে দ্বিতীয় (সমান জরুরি) মোচড়: reverse loop চালালে n ভেঙে গিয়ে 0 হয়ে যায়, তাই তুলনা করার মতো আসল সংখ্যাটা আগেই আলাদা করে রাখতে হবে (original = n)। এই copy রাখাটা না করা level 0-এর সবচেয়ে কমন bug — একবার এই ফাঁদে পড়লে আর ভুলবে না।

11. Step-by-step dry run¶

n = 121। আগে original = 121 সরিয়ে রাখি (অটুট থাকবে)। তারপর reverse loop:

step	n (শুরুতে)	n % 10	rev = rev*10 + (n%10)	n //= 10 (পরে)
1	121	1	0×10 + 1 = 1	12
2	12	2	1×10 + 2 = 12	1
3	1	1	12×10 + 1 = 121	0

ধাপ 3-এর শেষে n = 0, loop থামল। এখন তুলনা: rev (121) == original (121) → True → palindrome।

এবার মনে মনে n = 123 চালাও: rev হবে 321, তারপর 321 == 123 → False। আর n = 10: rev = 1 (01 = 1), 1 == 10 → False — ঠিক।

12. Python solution¶

def is_palindrome(n):
    """n palindrome হলে True, নাহলে False (arithmetic পদ্ধতি)।"""
    if n < 0:
        return False            # negative কখনো palindrome নয়
    original = n                # মূলটা মনে রাখো — n ভেঙে যাবে!
    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n //= 10
    return rev == original


def is_palindrome_str(n):
    """একই উত্তর, string পদ্ধতি (তুলনার জন্য)।"""
    if n < 0:
        return False
    s = str(n)
    return s == s[::-1]


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert is_palindrome(121) is True
assert is_palindrome(1331) is True
assert is_palindrome(123) is False
assert is_palindrome(7) is True       # এক digit
assert is_palindrome(0) is True       # 0 palindrome
assert is_palindrome(-121) is False   # negative নয়
assert is_palindrome(10) is False     # উল্টালে 1, 10 নয়
assert is_palindrome_str(121) is True     # দুই পদ্ধতি মেলে
assert is_palindrome_str(-121) is False

print(is_palindrome(121))    # True
print(is_palindrome(123))    # False
print(is_palindrome(-121))   # False
print("সব test pass!")

13. Line-by-line explanation¶

    if n < 0:
        return False

negative হলে সাথে সাথে False — কারণ minus চিহ্ন উল্টালে সংখ্যা আর মেলে না (-121 ≠ 121-)। এটা সবার আগে চেক করি যাতে পরের loop-এ ঝামেলা না হয়।

    original = n

এই problem-এর প্রাণভোমরা। reverse loop নিচে n-কে ভেঙে 0 বানিয়ে ফেলবে, তাই তুলনা করার জন্য মূল সংখ্যাটা আগেই আলাদা পাত্রে তুলে রাখি। এই লাইন বাদ দিলে শেষে rev == n হবে rev == 0 — সবসময় ভুল।

    rev = 0
    while n > 0:
        rev = rev * 10 + n % 10
        n //= 10

হুবহু 004-এর reverse loop। n % 10 last digit তোলে, rev * 10 + ... বামে ঠেলে ডানে বসায়, n //= 10 ফেলে দেয়। শেষে rev-এ থাকে উল্টানো সংখ্যা।

    return rev == original

উল্টানো সংখ্যা মূলের সমান হলে True (palindrome), নাহলে False। == নিজেই একটা True/False দেয়, তাই সরাসরি return।

is_palindrome_str হলো shortcut — s == s[::-1] string-টা তার উল্টোটার সাথে মেলায়, negative আগে আলাদা করে বাদ দিয়ে।

14. Output walkthrough¶

চালালে ছাপবে:

True
False
False
সব test pass!

তিনটা মান তিনটা print থেকে: is_palindrome(121) → True, is_palindrome(123) → False, is_palindrome(-121) → False (negative)। তার আগে সব assert চুপচাপ pass করেছে (একটাও fail করলে সেখানেই থেমে error দিত)। শেষ লাইন সব test pass! মানে দুই পদ্ধতির উত্তর মিলেছে, সব ঠিক।

15. Time complexity¶

O(number of digits) = O(log₁₀ n)। reverse loop প্রতিবার n-কে 10 দিয়ে ভাগ করে, তাই digit সংখ্যার সমান ঘোরে; শেষের তুলনাটা O(1)। 9-digit সংখ্যাতেও মাত্র 9 ধাপ — খুবই দ্রুত।

16. Space complexity¶

O(1) — arithmetic version-এ শুধু original, rev, n — গুটিকয় variable, সংখ্যার আকারের সাথে বাড়ে না। (string version-এ O(digit) — দুটো string মেমরিতে বানায়।)

17. Common mistakes¶

original = n রাখতে ভুলে যাওয়া — এই problem-এর এক নম্বর ফাঁদ। reverse loop n-কে 0 বানিয়ে ফেলে, তাই আগে copy না রাখলে শেষে ভুল তুলনা (rev == 0) হয়। সবসময় আগে মূলটা সরিয়ে রাখো।
negative ভুলে যাওয়া — -121 palindrome নয়; শুরুতেই if n < 0: return False না বসালে loop ভুল উত্তর দেবে (while -121 > 0 মিথ্যা, rev = 0, 0 == -121 False — এখানে কাকতালীয়ভাবে ঠিক, কিন্তু অভ্যাস হিসেবে স্পষ্ট চেক রাখা নিরাপদ)।
n //= 10 ভুলে যাওয়া — তাহলে loop কখনো থামবে না → infinite loop।
rev = rev * 10 + ...-এর * 10 বাদ দেওয়া — তাহলে reverse না হয়ে digit sum হয়ে যায়, তুলনা সব ভুল।
trailing zero ভুলে যাওয়া — 10, 100 palindrome নয় (উল্টালে 1 হয়)। শুধু 0 নিজে palindrome।

18. Harder problems that inherit this idea¶

LeetCode — Palindrome Number (https://leetcode.com/problems/palindrome-number/) — এই problem-টাই; follow-up হিসেবে string ছাড়া করতে বলে, যেটা আমরা arithmetic version-এ করেছি (এমনকি "অর্ধেক reverse" করেও করা যায়)।
LeetCode — Valid Palindrome (https://leetcode.com/problems/valid-palindrome/) — string-এর জগতে একই idea: দুই প্রান্ত থেকে মিলিয়ে এগোনো (two-pointer), reverse-এরই আত্মীয়।
LeetCode — Palindrome Linked List (https://leetcode.com/problems/palindrome-linked-list/) — এখানে "উল্টে মেলাও" idea linked list-এ ফেরে; reverse + compare-এর সরাসরি বড় ভাই।

19. Pattern learned¶

Reverse + compare — কোনো জিনিস palindrome কিনা জানতে তার একটা reverse বানিয়ে original-এর সাথে মেলাও। সাথে দুটো দামি শিক্ষা: (১) আগের problem (004 reverse) এখানে উত্তরের অর্ধেক হয়ে বসে ছিল — inherits-from column সত্যিই কাজে লাগে; (২) যে variable-কে loop ভেঙে ফেলবে, তার মূল মান আগেই copy করে রাখতে হয় — এই অভ্যাস পরের অনেক problem-এ বাঁচাবে।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "palindrome = 004-এর reverse বানাও, তারপর rev == original মেলাও। দুটো জিনিস ভুলো না — আগে original = n copy রাখো (n ভেঙে যাবে), আর negative সবসময় False।"

আগের ধাপ → 004 — Reverse Number (যেখান থেকে reverse loop পেলাম)। শিকড়ে → 002 — Sum of Digits · 001 — Even or Odd।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" লেখা।