Problem link ও উৎস
- Original source: LeetCode — Palindrome Number —
- Platform: LeetCode —
- Topic: Math-based programming fundamentals → Level 0: Absolute Basics
- Difficulty: Easy
- Pattern: reverse + compare
- Basic idea inherited from: 004 (Reverse Number)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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 চিহ্ন সামনে থাকে, পেছনে নয়)।
### Input ও output {#6-example-input-and-output}
```text
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-এর সমান নয়)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার হাতে একটা **পুঁতির মালা**, আর তুমি দেখতে চাও মালাটা **প্রতিসম (symmetric)** কিনা — মানে এক প্রান্ত থেকে পড়লে আর উল্টো প্রান্ত থেকে পড়লে রঙের ক্রম একই কিনা।
- তুমি মালাটার একটা হুবহু নকল বানাও, কিন্তু **উল্টো দিক থেকে** গেঁথে → এটাই reverse বানানো
- এবার আসল মালা আর উল্টো মালা **পাশাপাশি রেখে মেলাও** → এটাই `rev == original`
- দুটো হুবহু এক দেখালে → মালা প্রতিসম → palindrome
খুব জরুরি: নকল বানানোর আগে **আসল মালাটা সরিয়ে রাখতে হবে**, নাহলে গাঁথতে গাঁথতে আসলটাই খুলে যাবে — মেলাবে কীসের সাথে? এটাই code-এ `original = n` রাখার কারণ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-টা এখানে উত্তরের অর্ধেক হয়ে বসে আছে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
কোনো নতুন গণিত নেই — পুরোটাই 004-এর reverse, তার উপর একটা তুলনা। চিন্তা তিন ধাপে:
1. মূল সংখ্যাটা আলাদা করে **মনে রাখো** (copy)
2. সংখ্যাটা **উল্টে ফেলো** (004-এর `rev = rev * 10 + d` loop)
3. উল্টানো সংখ্যা মূল সংখ্যার সমান হলে palindrome, নাহলে নয়
```
original = n # মূলটা মনে রাখো (n তো ভেঙে যাবে!)
rev = 0
যতক্ষণ n > 0:
rev = rev * 10 + n % 10
n //= 10
return rev == original
```
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে যেটা মাথায় আসে — সংখ্যাটাকে **string বানিয়ে** তার উল্টোটার সাথে সরাসরি মেলাই:
```python
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 চালিয়ে, তারপর মূলের সাথে মেলাই:
```python
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 — একবার এই ফাঁদে পড়লে আর ভুলবে না।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 121` reverse হচ্ছে, পাশে original অপরিবর্তিত বসে আছে — শেষে দুজনে মেলে:
```text
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, যেখানে শেষে তুলনা ফেল করে:
```text
original = 123 (অটুট)
n = 123 -> rev = 3 n = 12 -> rev = 32 n = 1 -> rev = 321
মেলাও: rev (321) == original (123) -> False -> palindrome নয়
```
### ছোট input-এ ধাপে ধাপে {#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 — ঠিক।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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 আগে আলাদা করে বাদ দিয়ে।
### Output মিলিয়ে দেখা {#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!` মানে দুই পদ্ধতির উত্তর মিলেছে, সব ঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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}
1. **`original = n` রাখতে ভুলে যাওয়া** — এই problem-এর এক নম্বর ফাঁদ। reverse loop `n`-কে 0 বানিয়ে ফেলে, তাই আগে copy না রাখলে শেষে ভুল তুলনা (`rev == 0`) হয়। সবসময় আগে মূলটা সরিয়ে রাখো।
2. **negative ভুলে যাওয়া** — `-121` palindrome নয়; শুরুতেই `if n < 0: return False` না বসালে loop ভুল উত্তর দেবে (`while -121 > 0` মিথ্যা, rev = 0, `0 == -121` False — এখানে কাকতালীয়ভাবে ঠিক, কিন্তু অভ্যাস হিসেবে স্পষ্ট চেক রাখা নিরাপদ)।
3. **`n //= 10` ভুলে যাওয়া** — তাহলে loop কখনো থামবে না → infinite loop।
4. **`rev = rev * 10 + ...`-এর `* 10` বাদ দেওয়া** — তাহলে reverse না হয়ে digit sum হয়ে যায়, তুলনা সব ভুল।
5. **trailing zero ভুলে যাওয়া** — `10`, `100` palindrome নয় (উল্টালে 1 হয়)। শুধু `0` নিজে palindrome।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Palindrome Number** (