006 — Armstrong Number¶
এতক্ষণ আমরা digit extraction loop-টা নানাভাবে ঘুরিয়ে দেখেছি — যোগ (002), গোনা (003), বানানো (004)। আজকের problem-এ সেই একই loop, কিন্তু "প্রতি ধাপে কী করব" অংশে এবার একটা মজার মোচড় — digit-কে power-এ তুলে যোগ। 153 = 1³ + 5³ + 3³ — সংখ্যাটা নিজের কাছেই ফিরে আসে! এই "self-referential" সৌন্দর্যটাই Armstrong number-কে এত মজার করে তোলে।
Source¶
- 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)
1. Problem in simple words¶
একটা integer n দেওয়া আছে। বলতে হবে এটা Armstrong number কিনা।
নিয়ম: সংখ্যাটায় যতগুলো digit আছে (ধরো k টা), প্রতিটা digit-কে k-তম power-এ তোলো, সব যোগ করো — যোগফল যদি মূল সংখ্যার সমান হয়, তবেই Armstrong।
যেমন 153-এ digit তিনটে (k = 3):
আবার 9474-এ digit চারটে (k = 4): 9⁴ + 4⁴ + 7⁴ + 4⁴ = 6561 + 256 + 2401 + 256 = 9474 — হ্যাঁ, এটাও Armstrong। (এদের narcissistic number-ও বলে — নিজের প্রেমে পড়া সংখ্যা!)
2. What is the math idea?¶
দুটো জিনিস লাগবে — দুটোই আমরা আগে দেখেছি:
- সংখ্যায় কয়টা digit (
k) — এটা 003-এর digit count। - প্রতিটা 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-তে তুলি, আর দেখি কাকতালীয়ভাবে যোগফল মূল সংখ্যায় ফেরে কিনা।
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) — দুই পুরোনো বন্ধুই এখানে কাজে লাগছে।
4. Real-life analogy¶
ভাবো একটা মুদ্রা যাচাইয়ের পরীক্ষা। তোমাকে কেউ বলল — "এই বিশেষ সংখ্যাটার প্রতিটা digit-কে একটা নির্দিষ্ট নিয়মে রূপান্তর করে যোগ করলে, আশ্চর্যজনকভাবে আবার মূল সংখ্যাটাই ফিরে আসে। যাচাই করো তো সত্যি কিনা।"
- নিয়মটা হলো: প্রতিটা digit-কে (মোট digit সংখ্যা)-তম power-এ তোলো →
d ** k - সব রূপান্তরিত মান যোগ করো →
total - এবার মিলিয়ে দেখো যোগফল মূল সংখ্যার সমান কিনা →
total == n
মিলে গেলে সংখ্যাটা এই গোপন পরীক্ষায় পাস — Armstrong। এটা অনেকটা "এই সংখ্যাটার কি একটা লুকোনো প্রতিসাম্য আছে?" — সেই প্রশ্নের যাচাই।
5. Visual explanation¶
n = 153 (k = 3)। digit গুলো বেরোচ্ছে ডান থেকে, প্রতিটা cube হয়ে total-এ জমছে:
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, যেখানে শেষে মেলে না:
n = 100, k = 3
d = 0 -> 0³ = 0 d = 0 -> 0 d = 1 -> 1³ = 1
total = 1
মেলাও: total (1) == n (100) -> False -> Armstrong নয়
6. Example input and output¶
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।
7. Brute force thinking¶
এখানে "brute force বনাম optimal" তেমন বড় ফারাক নেই (digit কম, কাজ কম), কিন্তু সবচেয়ে সরাসরি পদ্ধতি — string বানিয়ে digit আর digit-সংখ্যা দুটোই সহজে পাওয়া:
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 মোচড় দিয়ে):
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-এ।)
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)।
12. Python solution¶
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¶
003-এর সেই চেনা digit-গোনা function — power কত হবে (k) সেটা জানতে দরকার। n = 0 হলে আলাদা করে 1 ফেরায়।
Armstrong সাধারণত শুধু non-negative সংখ্যার জন্য সংজ্ঞায়িত, তাই negative হলে সাথে সাথে False।
এই problem-এর মূল চাবি — power-টা মোট digit সংখ্যার সমান, fixed নয়। তাই power-sum শুরুর আগে k বের করে নিই।
চেনা digit extraction loop, কিন্তু total += d ** k — digit-এর মান নয়, k-তম power যোগ করছি। temp ব্যবহার করছি যাতে মূল 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 এক লাইনে।
14. Output walkthrough¶
চালালে ছাপবে:
তিনটা মান তিনটা print থেকে: is_armstrong(153) → True, is_armstrong(9474) → True, is_armstrong(123) → False। তার আগে সব assert চুপচাপ pass করেছে (একটাও fail করলে সেখানেই থেমে error দিত)। শেষ লাইন সব test pass! মানে দুই পদ্ধতির উত্তর মিলেছে, সব ঠিক।
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¶
- power-কে fixed 3 ধরা — সবচেয়ে কমন ভুল। power সবসময় মোট digit সংখ্যা;
9474-এ power 4,153-এ 3। আগেkগুনে নাও। - মূল
n-কে loop-এ ভেঙে ফেলা — power-sum loop-এ আলাদাtempব্যবহার করো, নাহলে শেষে তুলনার জন্যnআর থাকবে না (palindrome-এরoriginal = n-এর মতোই ফাঁদ)। ** kভুলে* kলেখা —d * kমানে গুণ,d ** kমানে power। দুটো সম্পূর্ণ আলাদা; Armstrong-এ চাই power।temp //= 10ভুলে যাওয়া — তাহলে loop কখনো থামবে না → infinite loop।- digit count loop-এ
n = 0ভুলে যাওয়া — 0-এর digit সংখ্যা 1, আলাদা handle না করলে k = 0 হয়ে গোলমাল (যদিও এখানে n=0-এ power-sum loop চলেই না, তবু count function-টা সঠিক রাখা ভালো অভ্যাস)।
18. Harder problems that inherit this idea¶
- LeetCode — Happy Number (https://leetcode.com/problems/happy-number/) — এখানে digit-এর বর্গের যোগফল বারবার নিতে হয় যতক্ষণ না 1 আসে (বা চক্র ধরা পড়ে); ভেতরের ইঞ্জিন এই digit power-sum loop।
- 002 — Sum of Digits (এই repo) — Armstrong-এর সরল পূর্বপুরুষ; power = 1 ধরলে Armstrong-এর power-sum-ই sum of digits।
- LeetCode — Add Digits (https://leetcode.com/problems/add-digits/) ও এই repo-র 007 — Digital Root — digit নিয়ে বারবার কাজ করার একই extraction পরিবার।
19. Pattern learned¶
Digit power sum — digit extraction loop-এর ভেতরে += d বদলে += d ** k, যেখানে k = মোট digit সংখ্যা। বড় শিক্ষা: একই loop-এর "কাজে লাগাও" লাইনটা বদলেই sum → count → power-sum সব পাওয়া যায়। আর এখানে দুই পুরোনো problem (002 sum + 003 count) একসাথে কাজে লাগল — পুরোনো হাতিয়ার জোড়া দিলেই নতুন problem।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "Armstrong = আগে digit গুনে k বের করো, তারপর extraction loop-এ total += d ** k, শেষে total == n মেলাও। power fixed নয়, = digit সংখ্যা; মূল n অটুট রাখতে আলাদা temp চালাও।"
আগের ধাপ → 002 — Sum of Digits (extraction loop) · 003 — Count Digits (k গোনা)। শিকড়ে → 001 — Even or Odd। সম্পর্কিত → 007 — Digital Root।
ফিরে দেখা: এই 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" লেখা।