007 — Digital Root

002-এ একবার digit যোগ করেছিলাম। আজ সেটা বারবার করব — যোগফল এক digit না হওয়া পর্যন্ত। 9875 → 29 → 11 → 2। এটুকু হলো সহজ অংশ। কিন্তু এই problem-এর আসল রত্ন হলো একটা চমকে দেওয়া shortcut — 1 + (n - 1) % 9 — যেটা পুরো loop-টাকে এক লাইনে নামিয়ে দেয়। % 9-এর এই জাদু বুঝে গেলে modular arithmetic-এর জগতে তোমার প্রথম পা পড়ে যাবে। ধীরে যাও, dry run-টা নিজে করো।

Source

• Original source: Classic exercise (related practice: LeetCode — Add Digits — https://leetcode.com/problems/add-digits/)
• Platform: Classic exercise / LeetCode (related)
• Topic: Math-based programming fundamentals → Level 0: Absolute Basics
• Difficulty: Easy
• Pattern: repeated digit sum, mod 9
• Basic idea inherited from: 002 (Sum of Digits)

1. Problem in simple words

একটা non-negative integer n দেওয়া আছে। তার digital root বের করতে হবে।

নিয়ম: সব digit যোগ করো। যোগফল যদি এক-digit হয় (0-9), সেটাই উত্তর। নাহলে সেই যোগফলের digit আবার যোগ করো — এভাবে চলতে থাকো যতক্ষণ না এক digit থাকে।

যেমন 9875:

9875  ->  9+8+7+5 = 29
  29  ->  2+9     = 11
  11  ->  1+1     = 2     <- এক digit, থামো! digital root = 2

2. What is the math idea?

দুটো স্তরে বোঝা যায় — সহজ আর জাদু:

সহজ (loop): 002-এর digit sum loop-টাই, কিন্তু একবার নয় — বারবার, যতক্ষণ না সংখ্যাটা এক digit (< 10) হয়।

যতক্ষণ n >= 10:
    n = (n-এর digit গুলোর যোগফল)
return n

জাদু (mod 9): আসলে digital root-এর একটা গোপন সূত্র আছে — % 9-এর সাথে গভীর সম্পর্ক। উত্তর সবসময় 1 থেকে 9-এর মধ্যে ঘোরে (n = 0 হলে 0), আর সেটা ধরা যায় এক লাইনে:

digital_root(n) = 0          যদি n == 0
                = 1 + (n-1) % 9   নাহলে

কেন % 9? কারণ 10 % 9 = 1, 100 % 9 = 1 — মানে প্রতিটা place value 9-এর জগতে 1-এর সমান। তাই একটা সংখ্যা আর তার digit sum, mod 9-এ সবসময় একই থাকে। বারবার digit যোগ করলেও mod 9 বদলায় না — শেষে যে এক-digit সংখ্যাটা থাকে, সেটাই mod 9-এর প্রতিনিধি।

3. Which basic idea does this inherit from?

সরাসরি 002 (Sum of Digits) থেকে — ভেতরের digit sum loop হুবহু 002-এর।

002 আর 007-এর সম্পর্ক এক বাক্যে:

002:  digit sum একবার নাও          -> 9875 হলে 29
007:  digit sum বারবার নাও         -> 9875 -> 29 -> 11 -> 2
      যতক্ষণ না এক digit থাকে

মানে 007 হলো 002-কে একটা বাইরের loop-এ মুড়ে দেওয়া — "digit sum নাও, যদি বড় থাকে আবার নাও"। আগের problem-টা এখানে ভেতরের ইঞ্জিন হয়ে কাজ করছে। আর % 9-এর shortcut-টা concept-notes-এ যে "mod-এর জাদু" দেখেছিলে, তারই সরাসরি প্রয়োগ।

4. Real-life analogy

ভাবো একটা ভাঁজ করা কাগজ। তোমাকে একটা বড় সংখ্যা দেওয়া হলো, আর বলা হলো — "এটাকে ছোট করতে থাকো, প্রতিবার digit গুলো যোগ করে, যতক্ষণ না হাতের তালুতে ধরার মতো এক-অঙ্কের একটা সংখ্যা থাকে।"

• প্রতিটা ভাঁজ = একবার digit যোগ করা (সংখ্যা ছোট হলো)
• কাগজ যথেষ্ট ছোট (এক digit) হলে → থামো; হাতে যা রইল সেটাই digital root

আর mod 9-এর জাদুটা হলো — তুমি কাগজটা না ভাঁজ করেই বলে দিতে পারো শেষে কী থাকবে! কারণ digit যোগ করা সংখ্যার "9-এর জগতের পরিচয়" বদলায় না। অনেকটা accountant-দের পুরোনো "casting out nines" কৌশল — হিসাব ঠিক আছে কিনা যাচাই করতে digit যোগ করে 9 দিয়ে মেলানো।

5. Visual explanation

n = 9875 ধাপে ধাপে ছোট হচ্ছে, প্রতিটা ধাপে digit sum নিয়ে:

9875  --(9+8+7+5)-->  29   (>= 10, চালিয়ে যাও)
  29  --(2+9)------>  11   (>= 10, চালিয়ে যাও)
  11  --(1+1)------>   2   (< 10, থামো!)

digital root = 2

এবার mod 9 shortcut একই উত্তরে পৌঁছায় — এক লাফে:

1 + (9875 - 1) % 9
= 1 + 9874 % 9
= 1 + 1          (9874 = 9×1097 + 1, তাই remainder 1)
= 2              <- হুবহু loop-এর উত্তর!

কেন মেলে? কারণ প্রতি ধাপে digit sum নিলেও n % 9 একই থাকে — loop শুধু সেই mod 9 মানটাকেই খুঁজে বের করছে, ধীরে ধীরে।

6. Example input and output

input   ->  output   (কীভাবে)
------------------------------
 9875   ->    2      (9875 -> 29 -> 11 -> 2)
   38   ->    2      (3+8 = 11 -> 1+1 = 2)
    0   ->    0      <-- একমাত্র 0 যেখানে উত্তর 0
    9   ->    9      (এক digit, নিজেই)
   18   ->    9      (1+8 = 9)
   99   ->    9      (9+9 = 18 -> 1+8 = 9)
  123   ->    6      (1+2+3 = 6)

দুটো জিনিস খেয়াল করো: উত্তর সবসময় 1 থেকে 9 (শুধু n = 0 হলে 0), আর 9-এর গুণিতকের digital root সবসময় 9 (18, 99, 9 — সব 9)। এই দুটোই mod 9-এর জাদুর সরাসরি ফল।

7. Brute force thinking

সবচেয়ে সৎ, সরাসরি পদ্ধতি — 002-এর digit sum-টাকে একটা বাইরের loop-এ বসিয়ে বারবার চালাই, যতক্ষণ না এক digit থাকে:

def digital_root_loop(n):
    n = abs(n)
    while n >= 10:           # যতক্ষণ একাধিক digit
        s = 0
        while n > 0:         # ভেতরের 002-এর digit sum loop
            s += n % 10
            n //= 10
        n = s                # যোগফলকে নতুন n ধরো, আবার পরীক্ষা করো
    return n

ভেতরের loop digit sum করে, বাইরের loop সেটা বারবার চালায়। পরিষ্কার, ঠিক উত্তর দেয়, আর 002 জানলে সহজেই লেখা যায়।

8. Why brute force may be slow

সত্যি বলতে এই loop "ধীর" নয় — খুব দ্রুত এক digit-এ নেমে আসে (প্রতি ধাপে সংখ্যা নাটকীয়ভাবে ছোট হয়; কয়েক ধাপেই শেষ)। তাহলে আরও ভাবার দরকার কেন?

• পুনরাবৃত্ত কাজ: আমরা একই ধরনের digit sum বারবার করছি, অথচ গণিত বলছে শেষ উত্তরটা সরাসরি % 9 দিয়ে পাওয়া যায়। loop সেই সত্যকে ধীরে ধীরে আবিষ্কার করছে মাত্র।
• O(1)-এর হাতছানি: যদি সূত্রটা জানা থাকে, পুরো ব্যাপারটা এক ধাপে (একটা % আর একটা যোগ) হয়ে যায় — কোনো loop ছাড়াই। interview-তে এই "আমি pattern-টা চিনি" দেখানোটাই মূল্যবান।

মূল শিক্ষা ধীরগতি নয় — একটা গাণিতিক pattern (mod 9) চিনতে পারলে loop পুরো বাদ দেওয়া যায়। চলো সেই জাদুটা দেখি।

9. Better thinking

মূল observation: digit sum নিলে সংখ্যার % 9 মান বদলায় না, তাই বারবার digit sum-এর শেষ ফলটা আসলে % 9-এরই একটা রূপ। সরাসরি সূত্র:

def digital_root(n):
    n = abs(n)
    if n == 0:
        return 0
    return 1 + (n - 1) % 9

কেন 1 + (n - 1) % 9, সোজা n % 9 নয়? কারণ n % 9 9-এর গুণিতকে 0 দেয় (যেমন 18 % 9 = 0), অথচ digital root চায় 9। (n - 1) % 9 দিয়ে রেঞ্জটা 0-8-এ আনি, তারপর +1 করে 1-9-এ তুলি — ফলে 9-এর গুণিতকেও ঠিক 9 আসে। এটা O(1) — কোনো loop নেই।

10. Thinking tweak

আসল "আহা!" মুহূর্ত এক বাক্যে: digit যোগ করলে সংখ্যার % 9 মান বদলায় না — তাই বারবার digit যোগ করে এক-অঙ্কে নামার শেষ ফলটা আসলে % 9-ই (9-এর গুণিতকে 9, n = 0 হলে 0)।

কেন % 9 বদলায় না, এক ঝলক: 10 % 9 = 1, তাই 1234 = 1×1000 + 2×100 + 3×10 + 4 — mod 9-এ প্রতিটা place value 1-এর সমান, মানে 1234 % 9 = (1+2+3+4) % 9। সংখ্যা আর তার digit sum, mod 9-এ যমজ! এই একটা insight loop-টাকে এক লাইনে নামিয়ে দেয়। এই % 9-এর জাদু Level 2 (modular arithmetic)-এ পুরোপুরি খুলে দেখবে — আজ শুধু পরিচয়।

11. Step-by-step dry run

n = 9875। আগে brute force (যাতে চোখে দেখা যায়), পরে shortcut।

Brute force — বাইরের loop-এর প্রতি ধাপে ভেতরের digit sum:

বাইরের ধাপ	শুরুর n	digit sum	নতুন n	n >= 10?
1	9875	9+8+7+5 = 29	29	হ্যাঁ, চালাও
2	29	2+9 = 11	11	হ্যাঁ, চালাও
3	11	1+1 = 2	2	না, থামো

শেষে n = 2 → digital root = 2।

Shortcut — এক লাইনে:

1 + (9875 - 1) % 9  =  1 + 9874 % 9
9874 = 9 × 1097 + 1  ->  remainder 1
=  1 + 1  =  2

দুটোই 2 — একই সত্য, কিন্তু shortcut সোজা গন্তব্যে। নিজে খাতায় 38 দিয়ে দুই পথ মেলাও (loop: 11 → 2; formula: 1 + 37 % 9 = 1 + 1 = 2)।

12. Python solution

def digital_root(n):
    """n-এর digital root, O(1) mod-9 সূত্রে।"""
    n = abs(n)
    if n == 0:
        return 0
    return 1 + (n - 1) % 9


def digital_root_loop(n):
    """একই উত্তর, বারবার digit sum (002-এর loop-এর উপর)।"""
    n = abs(n)
    while n >= 10:
        s = 0
        while n > 0:
            s += n % 10
            n //= 10
        n = s
    return n


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert digital_root(9875) == 2     # 9875 -> 29 -> 11 -> 2
assert digital_root(38) == 2       # 38 -> 11 -> 2
assert digital_root(0) == 0        # একমাত্র 0-তে উত্তর 0
assert digital_root(9) == 9        # এক digit
assert digital_root(18) == 9       # 9-এর গুণিতক -> 9
assert digital_root(99) == 9       # 99 -> 18 -> 9
assert digital_root(123) == 6      # 1+2+3
# দুই পদ্ধতি সব ছোট সংখ্যায় মেলে কিনা যাচাই:
for x in range(0, 1000):
    assert digital_root(x) == digital_root_loop(x)

print(digital_root(9875))   # 2
print(digital_root(99))     # 9
print(digital_root(0))      # 0
print("সব test pass!")

13. Line-by-line explanation

    n = abs(n)

চিহ্ন সরিয়ে দিই, যাতে সূত্র আর loop দুটোই non-negative সংখ্যার উপর ঠিকমতো চলে।

    if n == 0:
        return 0

একমাত্র বিশেষ ক্ষেত্র। 0-এর digital root 0; সূত্র 1 + (n-1) % 9 0-তে ভুল দিত (1 + (-1) % 9 = 1 + 8 = 9), তাই আগেই আলাদা করে 0 ফেরাই।

    return 1 + (n - 1) % 9

এই problem-এর জাদুকরী লাইন। (n - 1) % 9 ফলটাকে 0-8 রেঞ্জে আনে, +1 সেটাকে 1-9-এ তোলে — তাই 9-এর গুণিতকেও সঠিক 9 আসে (সোজা n % 9 দিলে 0 আসত)।

def digital_root_loop(n):
    while n >= 10:
        s = 0
        while n > 0:
            s += n % 10
            n //= 10
        n = s
    return n

বাইরের while n >= 10 চালায় যতক্ষণ একাধিক digit; ভেতরের loop হুবহু 002-এর digit sum; n = s যোগফলকে নতুন n বানায়। এক digit-এ নামলে থামে। এটা ধীরে ধীরে সেই mod-9 মানেই পৌঁছায়।

শেষের for x in range(0, 1000) loop দুই পদ্ধতির উত্তর প্রতিটা সংখ্যায় মিলিয়ে দেখে — সূত্রটা সত্যিই loop-এর সমান কিনা তার পাকা প্রমাণ।

14. Output walkthrough

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

2
9
0
সব test pass!

তিনটা মান তিনটা print থেকে: digital_root(9875) → 2, digital_root(99) → 9 (9-এর গুণিতক), digital_root(0) → 0 (বিশেষ ক্ষেত্র)। তার আগে সব assert চুপচাপ pass করেছে — যার মধ্যে 0 থেকে 999 পর্যন্ত প্রতিটা সংখ্যায় দুই পদ্ধতির মিল যাচাইও আছে। শেষ লাইন সব test pass! মানে সূত্র আর loop হুবহু মেলে, সব ঠিক।

15. Time complexity

• সূত্র version: O(1) — একটা বিয়োগ, একটা %, একটা যোগ; সংখ্যা যত বড়ই হোক একই কাজ।
• loop version: O(log n) কার্যত আরও কম — প্রথম digit sum-ই সংখ্যাটাকে নাটকীয়ভাবে ছোট করে দেয় (যেমন 9875 → 29), তারপর মাত্র কয়েক ধাপ। তবু upper bound হিসেবে প্রথম sum-এর জন্য O(log n) ধরা হয়।

interview-তে সূত্রটা বলতে পারলে O(1) — সেটাই চমক।

16. Space complexity

O(1) — দুই version-এই গুটিকয় variable (n, s), সংখ্যার আকারের সাথে বাড়ে না। কোনো list বা string লাগছে না।

17. Common mistakes

1. সোজা n % 9 ফেরানো — সবচেয়ে কমন ভুল। 18 % 9 = 0, কিন্তু digital root 9। তাই 1 + (n - 1) % 9 লাগে, খালি n % 9 নয়।
2. n = 0 ভুলে যাওয়া — সূত্র 0-তে ভুল (1 + (-1) % 9 = 9) দেয়; আগে if n == 0: return 0 বসাও।
3. একবার মাত্র digit sum নেওয়া — digital root চায় বারবার যোগ যতক্ষণ এক digit; 9875-এর উত্তর 2, 29 নয়। বাইরের loop (বা সূত্র) ছাড়া ভুল হবে।
4. while n >= 10-এর জায়গায় while n > 10 — তাহলে n = 10-এ থেমে যাবে (অথচ 10 → 1 হওয়া উচিত)। সীমা >= 10 হতে হবে।
5. ভেতরের loop-এ n //= 10 ভুলে যাওয়া — তাহলে digit sum loop কখনো থামবে না → infinite loop।

18. Harder problems that inherit this idea

• LeetCode — Add Digits (https://leetcode.com/problems/add-digits/) — এটাই digital root, হুবহু; follow-up-এ O(1) (loop ছাড়া) চায় — মানে এই % 9 সূত্রটাই উত্তর।
• 006 — Armstrong Number (এই repo) আর LeetCode — Happy Number (https://leetcode.com/problems/happy-number/) — "digit নিয়ে কিছু করে বারবার চালানো" — একই repeated-digit-process পরিবার।
• Level 2 — Modular arithmetic (এই repo-র পরের দিকে) — % 9-এর এই জাদু সেখানে পুরোপুরি খোলে: divisibility rule (3, 9 দিয়ে ভাগ), checksum, casting out nines — সবের মূলে এই idea।

19. Pattern learned

Repeated digit sum = mod 9। digit যোগ করা সংখ্যার % 9 বদলায় না, তাই বারবার digit sum-এর শেষ ফল সরাসরি 1 + (n-1) % 9 (n = 0 হলে 0)। বড় শিক্ষা: একটা গাণিতিক ধর্ম (এখানে mod 9 invariance) চিনতে পারলে গোটা loop এক লাইনে নামানো যায়। এই "loop-এর পেছনের সূত্র খোঁজা" চোখটাই পরের অনেক optimization-এর চাবি।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "digital root = বারবার digit sum যতক্ষণ এক digit; কিন্তু shortcut 1 + (n-1) % 9 (n = 0 হলে 0), কারণ digit sum সংখ্যার % 9 বদলায় না। 9-এর গুণিতকে উত্তর 9 — তাই সোজা n % 9 নয়।"

আগের ধাপ → 002 — Sum of Digits (ভেতরের digit sum loop)। শিকড়ে → 001 — Even or Odd। সম্পর্কিত → 006 — Armstrong Number।

ফিরে দেখা: এই 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" লেখা।