Problem link ও উৎস
- Original source: Classic beginner exercise (Armstrong / narcissistic number)
- Platform: Classic exercise
- Topic: Math-based programming fundamentals → Level 0: Absolute Basics
- Difficulty: Easy
- Pattern: digit power sum
- Basic idea inherited from: 002 (Sum of Digits)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer `n` দেওয়া আছে। বলতে হবে এটা **Armstrong number** কিনা।
নিয়ম: সংখ্যাটায় যতগুলো digit আছে (ধরো `k` টা), প্রতিটা digit-কে `k`-তম power-এ তোলো, সব যোগ করো — যোগফল যদি মূল সংখ্যার সমান হয়, তবেই Armstrong।
যেমন `153`-এ digit তিনটে (k = 3):
```
1³ + 5³ + 3³ = 1 + 125 + 27 = 153 <- মূল সংখ্যার সমান, তাই Armstrong!
```
আবার `9474`-এ digit চারটে (k = 4): `9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474` — হ্যাঁ, এটাও Armstrong। (এদের narcissistic number-ও বলে — নিজের প্রেমে পড়া সংখ্যা!)
### Input ও output {#6-example-input-and-output}
```text
input -> output (কীভাবে)
------------------------------
153 -> True (1³+5³+3³ = 153)
370 -> True (3³+7³+0³ = 27+343+0 = 370)
9474 -> True (9⁴+4⁴+7⁴+4⁴ = 9474)
123 -> False (1³+2³+3³ = 1+8+27 = 36 ≠ 123)
5 -> True (এক digit: 5¹ = 5, সব এক-digit সংখ্যা Armstrong)
0 -> True (0¹ = 0)
100 -> False (1³+0+0 = 1 ≠ 100)
```
মনে রাখার মতো: **সব এক-digit সংখ্যা (0-9) Armstrong**, কারণ k = 1, আর `d¹ = d`। আর power-টা সবসময় **মোট digit সংখ্যা**, fixed 3 নয় — `9474`-এ power 4।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **মুদ্রা যাচাইয়ের পরীক্ষা**। তোমাকে কেউ বলল — "এই বিশেষ সংখ্যাটার প্রতিটা digit-কে একটা নির্দিষ্ট নিয়মে রূপান্তর করে যোগ করলে, আশ্চর্যজনকভাবে আবার মূল সংখ্যাটাই ফিরে আসে। যাচাই করো তো সত্যি কিনা।"
- নিয়মটা হলো: প্রতিটা digit-কে (মোট digit সংখ্যা)-তম power-এ তোলো → `d ** k`
- সব রূপান্তরিত মান যোগ করো → `total`
- এবার মিলিয়ে দেখো যোগফল মূল সংখ্যার সমান কিনা → `total == n`
মিলে গেলে সংখ্যাটা এই গোপন পরীক্ষায় পাস — Armstrong। এটা অনেকটা "এই সংখ্যাটার কি একটা লুকোনো প্রতিসাম্য আছে?" — সেই প্রশ্নের যাচাই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **002 (Sum of Digits)** থেকে — extraction loop হুবহু এক, সাথে 003-এর digit count মিশে আছে।
002 আর 006-এর ভেতরের লাইন পাশাপাশি:
```
002 (sum): total += d # digit-এর মান যোগ
006 (armstrong): total += d ** k # digit-এর k-তম power যোগ
^^^^^
শুধু এই অংশ আলাদা
```
দেখো — loop, peeling, সব এক। শুধু "digit নিয়ে কী করব" বদলেছে: মান যোগের বদলে power-এ তুলে যোগ। এটাই বারবার বলা সেই কথা — **একটা loop শিখলে কত problem এমনিই হাতে আসে।** 002 (sum) আর 003 (count) — দুই পুরোনো বন্ধুই এখানে কাজে লাগছে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
দুটো জিনিস লাগবে — দুটোই আমরা আগে দেখেছি:
1. সংখ্যায় **কয়টা digit** (`k`) — এটা 003-এর digit count।
2. প্রতিটা digit তুলে **k-তম power-এ তুলে যোগ** — এটা 002-এর digit sum loop, শুধু `+= d`-এর জায়গায় `+= d ** k`।
```
k = digit সংখ্যা
total = 0
যতক্ষণ temp > 0:
d = temp % 10
total += d ** k # digit-কে k power-এ তুলে যোগ
temp //= 10
return total == n
```
মূল গণিত: **place value নয়, power।** সাধারণ সংখ্যায় প্রতিটা digit place value (1, 10, 100...) দিয়ে গুণ হয়; Armstrong-এ আমরা সেটা ভুলে গিয়ে প্রতিটা digit-কে একই power `k`-তে তুলি, আর দেখি কাকতালীয়ভাবে যোগফল মূল সংখ্যায় ফেরে কিনা।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
এখানে "brute force বনাম optimal" তেমন বড় ফারাক নেই (digit কম, কাজ কম), কিন্তু সবচেয়ে সরাসরি পদ্ধতি — **string বানিয়ে** digit আর digit-সংখ্যা দুটোই সহজে পাওয়া:
```python
def is_armstrong_str(n):
s = str(n)
k = len(s) # কয়টা digit
total = sum(int(ch) ** k for ch in s) # প্রতিটা digit-কে k power-এ তুলে যোগ
return total == n
```
`len(s)` digit গুনে দেয়, আর প্রতিটা অক্ষরকে `int()` করে `** k`-তে তুলে `sum()` যোগ করে। পরিষ্কার, ঠিক উত্তর দেয়, পড়তেও সহজ।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
আবারও — time-এর দিক থেকে string version "ধীর" নয়, দুটোই digit সংখ্যার সমান কাজ করে। পার্থক্য সূক্ষ্ম:
- **বাড়তি জায়গা:** `str(n)` একটা নতুন string বানায় → O(digit) extra space। arithmetic version O(1) space-এ চলে (digit count আলাদা loop-এ বের করে নিলে)।
- **ভাষা-নির্ভরতা:** Python-এ `len(str(n))` আর `int(ch)` সহজ, কিন্তু C++/Java-তে string-এ যাওয়া-আসা ঝামেলার। arithmetic পদ্ধতি **যেকোনো ভাষায়** একই।
- **চিন্তার অনুশীলন:** এই level-এ লক্ষ্য digit extraction loop-টা আয়ত্ত করা; power-sum সেই loop-এর আরেকটা প্রয়োগ মাত্র।
মূল কথা: string version-এ দোষ নেই, কিন্তু arithmetic version লিখতে পারলে দেখা যায় তুমি digit count আর digit sum — দুই পুরোনো loop একসাথে চালাতে পারো।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
String বাদ — দুই ধাপে: আগে digit গুনি (003-এর loop), তারপর power-sum করি (002-এর loop, power মোচড় দিয়ে):
```python
def is_armstrong(n):
if n < 0:
return False # সাধারণত Armstrong শুধু non-negative-এ সংজ্ঞায়িত
# ধাপ 1: digit সংখ্যা k বের করো (003-এর loop)
temp, k = n, 0
if n == 0:
k = 1
while temp > 0:
k += 1
temp //= 10
# ধাপ 2: প্রতিটা digit-কে k power-এ তুলে যোগ (002-এর loop, মোচড় দিয়ে)
temp, total = n, 0
while temp > 0:
d = temp % 10
total += d ** k
temp //= 10
return total == n
```
কোনো string নেই — শুধু সংখ্যা আর দুটো চেনা loop। জায়গা লাগছে O(1)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল মোচড় এক বাক্যে: **digit extraction loop-এর ভেতরের `+= d`-কে `+= d ** k` বানিয়ে দাও, যেখানে `k` হলো মোট digit সংখ্যা — ব্যস, sum থেকে Armstrong।**
আর সাথে একটা সূক্ষ্ম কথা: power-টা **fixed না**, সংখ্যাভেদে বদলায় — `153`-এ 3, `9474`-এ 4। তাই power-sum শুরু করার **আগে** digit গুনে `k` ঠিক করে নিতে হবে। এই "আগে গুনি, পরে power-এ তুলি" দুই-ধাপি চিন্তাটাই এখানকার মূল মোচড়। (003 + 002 একসাথে — দুই পুরোনো হাতিয়ার এক problem-এ।)
### ছবিতে বোঝা {#5-visual-explanation}
`n = 153` (k = 3)। digit গুলো বেরোচ্ছে ডান থেকে, প্রতিটা cube হয়ে total-এ জমছে:
```text
n = 153, digit সংখ্যা k = 3, total = 0
step 1: d = 3 3³ = 27 total = 0 + 27 = 27 temp -> 15
step 2: d = 5 5³ = 125 total = 27 + 125 = 152 temp -> 1
step 3: d = 1 1³ = 1 total = 152 + 1 = 153 temp -> 0 (থামো!)
মেলাও: total (153) == n (153) -> True -> Armstrong!
```
একটা non-Armstrong, যেখানে শেষে মেলে না:
```text
n = 100, k = 3
d = 0 -> 0³ = 0 d = 0 -> 0 d = 1 -> 1³ = 1
total = 1
মেলাও: total (1) == n (100) -> False -> Armstrong নয়
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 153`। আগে ধাপ 1-এ digit গুনি:
| step | temp (শুরুতে) | k (পরে) | temp //= 10 (পরে) |
| --- | --- | --- | --- |
| 1 | 153 | 1 | 15 |
| 2 | 15 | 2 | 1 |
| 3 | 1 | 3 | 0 |
ধাপ 1 শেষ — **k = 3**। এবার ধাপ 2-এ power-sum (`d ** 3`):
| step | temp (শুরুতে) | d = temp % 10 | d³ | total (পরে) | temp //= 10 |
| --- | --- | --- | --- | --- | --- |
| 1 | 153 | 3 | 27 | 0 + 27 = 27 | 15 |
| 2 | 15 | 5 | 125 | 27 + 125 = 152 | 1 |
| 3 | 1 | 1 | 1 | 152 + 1 = 153 | 0 |
ধাপ 2 শেষে `total = 153`। তুলনা: `153 == 153` → **True** → Armstrong! নিজে খাতায় `370` দিয়ে দুই ধাপ চালাও (k = 3, total = 27+343+0 = 370)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def count_digits(n):
"""n-এ কয়টা digit (003-এর loop)।"""
n = abs(n)
if n == 0:
return 1
k = 0
while n > 0:
k += 1
n //= 10
return k
def is_armstrong(n):
"""n Armstrong হলে True, নাহলে False (arithmetic পদ্ধতি)।"""
if n < 0:
return False # Armstrong শুধু non-negative-এ
k = count_digits(n) # power = মোট digit সংখ্যা
total = 0
temp = n
while temp > 0:
d = temp % 10
total += d ** k # digit-কে k power-এ তুলে যোগ
temp //= 10
return total == n # n = 0 হলে total = 0, 0 == 0 -> True
def is_armstrong_str(n):
"""একই উত্তর, string পদ্ধতি (তুলনার জন্য)।"""
if n < 0:
return False
s = str(n)
k = len(s)
return sum(int(ch) ** k for ch in s) == n
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert is_armstrong(153) is True # 1³+5³+3³
assert is_armstrong(370) is True # 3³+7³+0³
assert is_armstrong(9474) is True # 9⁴+4⁴+7⁴+4⁴
assert is_armstrong(123) is False # 36 ≠ 123
assert is_armstrong(5) is True # এক digit
assert is_armstrong(0) is True # 0¹ = 0
assert is_armstrong(100) is False # 1 ≠ 100
assert is_armstrong_str(153) is True # দুই পদ্ধতি মেলে
assert is_armstrong_str(9474) is True
print(is_armstrong(153)) # True
print(is_armstrong(9474)) # True
print(is_armstrong(123)) # False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def count_digits(n):
...
```
003-এর সেই চেনা digit-গোনা function — power কত হবে (`k`) সেটা জানতে দরকার। `n = 0` হলে আলাদা করে 1 ফেরায়।
```
if n < 0:
return False
```
Armstrong সাধারণত শুধু non-negative সংখ্যার জন্য সংজ্ঞায়িত, তাই negative হলে সাথে সাথে False।
```
k = count_digits(n)
```
**এই problem-এর মূল চাবি** — power-টা মোট digit সংখ্যার সমান, fixed নয়। তাই power-sum শুরুর আগে `k` বের করে নিই।
```
total = 0
temp = n
while temp > 0:
d = temp % 10
total += d ** k
temp //= 10
```
চেনা digit extraction loop, কিন্তু `total += d ** k` — digit-এর *মান* নয়, *k-তম power* যোগ করছি। `temp` ব্যবহার করছি যাতে মূল `n` অটুট থাকে (শেষে তুলনায় লাগবে)।
```
return total == n
```
power-sum মূল সংখ্যার সমান হলে `True` (Armstrong), নাহলে `False`। (`n = 0` হলে loop চলে না, total = 0, `0 == 0` → True — ঠিক।)
`is_armstrong_str` হলো shortcut — `len(s)` দিয়ে k, আর `sum(int(ch) ** k for ch in s)` দিয়ে power-sum এক লাইনে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```
True
True
False
সব test pass!
```
তিনটা মান তিনটা `print` থেকে: `is_armstrong(153)` → True, `is_armstrong(9474)` → True, `is_armstrong(123)` → False। তার আগে সব `assert` চুপচাপ pass করেছে (একটাও fail করলে সেখানেই থেমে error দিত)। শেষ লাইন `সব test pass!` মানে দুই পদ্ধতির উত্তর মিলেছে, সব ঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(number of digits) = O(log₁₀ n)**। দুটো loop-ই (digit count আর power-sum) digit সংখ্যার সমান ঘোরে, তাই মোট এখনো O(log n)। প্রতি ধাপে `d ** k`-এর খরচ ধরছি ছোট ধ্রুবক (digit ছোট, power ছোট), তাই সাধারণ interview-র মাপে নিশ্চিন্তে O(log n)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — arithmetic version-এ শুধু `k`, `total`, `temp`, `d` — গুটিকয় variable, সংখ্যার আকারের সাথে বাড়ে না। (string version-এ O(digit) — পুরো string মেমরিতে বানায়।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **power-কে fixed 3 ধরা** — সবচেয়ে কমন ভুল। power সবসময় **মোট digit সংখ্যা**; `9474`-এ power 4, `153`-এ 3। আগে `k` গুনে নাও।
2. **মূল `n`-কে loop-এ ভেঙে ফেলা** — power-sum loop-এ আলাদা `temp` ব্যবহার করো, নাহলে শেষে তুলনার জন্য `n` আর থাকবে না (palindrome-এর `original = n`-এর মতোই ফাঁদ)।
3. **`** k` ভুলে `* k` লেখা** — `d * k` মানে গুণ, `d ** k` মানে power। দুটো সম্পূর্ণ আলাদা; Armstrong-এ চাই power।
4. **`temp //= 10` ভুলে যাওয়া** — তাহলে loop কখনো থামবে না → infinite loop।
5. **digit count loop-এ `n = 0` ভুলে যাওয়া** — 0-এর digit সংখ্যা 1, আলাদা handle না করলে k = 0 হয়ে গোলমাল (যদিও এখানে n=0-এ power-sum loop চলেই না, তবু count function-টা সঠিক রাখা ভালো অভ্যাস)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Happy Number** (