006 — Armstrong Number

এতক্ষণ আমরা digit extraction loop-টা নানাভাবে ঘুরিয়ে দেখেছি — যোগ (002), গোনা (003), বানানো (004)। আজকের problem-এ সেই একই loop, কিন্তু "প্রতি ধাপে কী করব" অংশে এবার একটা মজার মোচড় — digit-কে power-এ তুলে যোগ। 153 = 1³ + 5³ + 3³ — সংখ্যাটা নিজের কাছেই ফিরে আসে! এই "self-referential" সৌন্দর্যটাই Armstrong number-কে এত মজার করে তোলে।

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)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা 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

উদাহরণ

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।

চেনা উদাহরণে বোঝা

ভাবো একটা মুদ্রা যাচাইয়ের পরীক্ষা। তোমাকে কেউ বলল — "এই বিশেষ সংখ্যাটার প্রতিটা digit-কে একটা নির্দিষ্ট নিয়মে রূপান্তর করে যোগ করলে, আশ্চর্যজনকভাবে আবার মূল সংখ্যাটাই ফিরে আসে। যাচাই করো তো সত্যি কিনা।"

• নিয়মটা হলো: প্রতিটা digit-কে (মোট digit সংখ্যা)-তম power-এ তোলো → d ** k
• সব রূপান্তরিত মান যোগ করো → total
• এবার মিলিয়ে দেখো যোগফল মূল সংখ্যার সমান কিনা → total == n

মিলে গেলে সংখ্যাটা এই গোপন পরীক্ষায় পাস — Armstrong। এটা অনেকটা "এই সংখ্যাটার কি একটা লুকোনো প্রতিসাম্য আছে?" — সেই প্রশ্নের যাচাই।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

সরাসরি 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) — দুই পুরোনো বন্ধুই এখানে কাজে লাগছে।

ভেতরের অঙ্ক

দুটো জিনিস লাগবে — দুটোই আমরা আগে দেখেছি:

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-তে তুলি, আর দেখি কাকতালীয়ভাবে যোগফল মূল সংখ্যায় ফেরে কিনা।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

এখানে "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() যোগ করে। পরিষ্কার, ঠিক উত্তর দেয়, পড়তেও সহজ।

কোথায় বেশি কাজ হতে পারে

আবারও — 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 একসাথে চালাতে পারো।

আরও ভালোভাবে ভাবা

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)।

ভাবনার পরিবর্তন

আসল মোচড় এক বাক্যে: digit extraction loop-এর ভেতরের += d-কে += d ** k বানিয়ে দাও, যেখানে k হলো মোট digit সংখ্যা — ব্যস, sum থেকে Armstrong।

আর সাথে একটা সূক্ষ্ম কথা: power-টা fixed না, সংখ্যাভেদে বদলায় — 153-এ 3, 9474-এ 4। তাই power-sum শুরু করার আগে digit গুনে k ঠিক করে নিতে হবে। এই "আগে গুনি, পরে power-এ তুলি" দুই-ধাপি চিন্তাটাই এখানকার মূল মোচড়। (003 + 002 একসাথে — দুই পুরোনো হাতিয়ার এক problem-এ।)

ছবিতে বোঝা

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 নয়

ছোট input-এ ধাপে ধাপে

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)।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

উদাহরণ

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 মিলিয়ে দেখা

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

উদাহরণ

True
True
False
সব test pass!

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

খরচ ও সাধারণ ভুল

সময়

O(number of digits) = O(log₁₀ n)। দুটো loop-ই (digit count আর power-sum) digit সংখ্যার সমান ঘোরে, তাই মোট এখনো O(log n)। প্রতি ধাপে d ** k-এর খরচ ধরছি ছোট ধ্রুবক (digit ছোট, power ছোট), তাই সাধারণ interview-র মাপে নিশ্চিন্তে O(log n)।

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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-টা সঠিক রাখা ভালো অভ্যাস)।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

• 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 পরিবার।

কৌশলটি মনে রাখুন

Digit power sum — digit extraction loop-এর ভেতরে += d বদলে += d ** k, যেখানে k = মোট digit সংখ্যা। বড় শিক্ষা: একই loop-এর "কাজে লাগাও" লাইনটা বদলেই sum → count → power-sum সব পাওয়া যায়। আর এখানে দুই পুরোনো problem (002 sum + 003 count) একসাথে কাজে লাগল — পুরোনো হাতিয়ার জোড়া দিলেই নতুন problem।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখা।