Problem link ও উৎস
- Original source: Classic exercise (related practice: LeetCode — 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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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
```
### Input ও output {#6-example-input-and-output}
```text
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-এর জাদুর সরাসরি ফল।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **ভাঁজ করা কাগজ**। তোমাকে একটা বড় সংখ্যা দেওয়া হলো, আর বলা হলো — "এটাকে ছোট করতে থাকো, প্রতিবার digit গুলো যোগ করে, যতক্ষণ না হাতের তালুতে ধরার মতো এক-অঙ্কের একটা সংখ্যা থাকে।"
- প্রতিটা ভাঁজ = একবার digit যোগ করা (সংখ্যা ছোট হলো)
- কাগজ যথেষ্ট ছোট (এক digit) হলে → থামো; হাতে যা রইল সেটাই digital root
আর mod 9-এর জাদুটা হলো — তুমি কাগজটা না ভাঁজ করেই বলে দিতে পারো শেষে কী থাকবে! কারণ digit যোগ করা সংখ্যার "9-এর জগতের পরিচয়" বদলায় না। অনেকটা accountant-দের পুরোনো "casting out nines" কৌশল — হিসাব ঠিক আছে কিনা যাচাই করতে digit যোগ করে 9 দিয়ে মেলানো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এর জাদু" দেখেছিলে, তারই সরাসরি প্রয়োগ।
### ভেতরের অঙ্ক {#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-এর প্রতিনিধি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সৎ, সরাসরি পদ্ধতি — 002-এর digit sum-টাকে একটা বাইরের loop-এ বসিয়ে বারবার চালাই, যতক্ষণ না এক digit থাকে:
```python
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`-এরই একটা রূপ। সরাসরি সূত্র:
```python
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)-এ পুরোপুরি খুলে দেখবে — আজ শুধু পরিচয়।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 9875` ধাপে ধাপে ছোট হচ্ছে, প্রতিটা ধাপে digit sum নিয়ে:
```text
9875 --(9+8+7+5)--> 29 (>= 10, চালিয়ে যাও)
29 --(2+9)------> 11 (>= 10, চালিয়ে যাও)
11 --(1+1)------> 2 (< 10, থামো!)
digital root = 2
```
এবার mod 9 shortcut একই উত্তরে পৌঁছায় — এক লাফে:
```text
1 + (9875 - 1) % 9
= 1 + 9874 % 9
= 1 + 1 (9874 = 9×1097 + 1, তাই remainder 1)
= 2 <- হুবহু loop-এর উত্তর!
```
কেন মেলে? কারণ প্রতি ধাপে digit sum নিলেও `n % 9` একই থাকে — loop শুধু সেই mod 9 মানটাকেই খুঁজে বের করছে, ধীরে ধীরে।
### ছোট input-এ ধাপে ধাপে {#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`)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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-এর সমান কিনা তার পাকা প্রমাণ।
### Output মিলিয়ে দেখা {#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 হুবহু মেলে, সব ঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Add Digits** (