Problem link ও উৎস
- **Original source:** Classic exercise (big number modulo, digit-by-digit)
- **Platform:** Classic exercise — CP intro আর interview-তে সাধারণ (string হিসেবে বিশাল সংখ্যা)
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Medium
- **Pattern:** digit-by-digit mod (Horner-style)
- **Basic idea inherited from:** 026 — Remainder Basics (clock model); সঙ্গে 027-এর প্রতি step-এ mod
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **বিশাল সংখ্যা** string হিসেবে দেওয়া (যেমন `"123456789012345678901234567890"`) আর একটা ছোট `m`। বের করতে হবে সেই বিশাল সংখ্যা `% m`।
কেন string? কারণ সংখ্যাটা এত বড় যে অনেক ভাষায় (C++/Java) কোনো int type-এই ধরে না। Python-এ ধরে, কিন্তু আমরা একটা ভাষা-নিরপেক্ষ, দ্রুত উপায় শিখব — যেটা সংখ্যাকে কখনো পুরো বড় হতে দেয় না।
### Input ও output {#6-example-input-and-output}
```text
s (string) m -> s % m check
-----------------------------------------------------------
"1234" 7 -> 2 1234 = 7×176+2
"100" 9 -> 1 100 = 9×11+1
"123456789012345678901" 1000 -> 901 শেষ 3 digit (mod 1000)
"0" 5 -> 0
"999999999999" 7 -> ? (নিজে int(s)%m মিলাও)
```
মজার edge case: `mod 1000` মানে আসলে শেষ 3 digit — কারণ 1000 = 10³, আর উপরের সব digit 10³-এর গুণিতকে চলে যায়। আমাদের loop এটা আপনাআপনি বের করে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা **odometer (গাড়ির মাইল-মিটার)** যেটা শুধু 0 থেকে m−1 পর্যন্ত গুনতে পারে, তারপর আবার 0-তে ফেরে। তুমি একটা বিশাল দূরত্ব digit ধরে ধরে ঢোকাচ্ছ।
প্রতিবার একটা নতুন digit ঢোকানো মানে: আগের পুরো সংখ্যাকে 10 গুণ করে (এক ঘর বাঁয়ে সরিয়ে) নতুন digit যোগ। কিন্তু odometer-টা ছোট — তাই প্রতিবার সে নিজে নিজে চক্কর ফেলে শুধু "শেষ অবস্থান" রাখে (`% m`)। শেষ digit ঢোকানো হলে odometer-এ যা দেখাচ্ছে সেটাই পুরো সংখ্যা mod m। সে কখনো বিশাল সংখ্যাটা মনে রাখেনি — শুধু ছোট remainder।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুটো শিকড় একসাথে:
- **026 — Remainder Basics** + 027/028-এর "প্রতি step-এ mod": যোগ-গুণে mod নিলেও উত্তর একই — সেটাই এখানে প্রতি digit-এ প্রয়োগ।
- **Level 0-এর number building** (`rev = rev*10 + d`): সেখানে তুমি digit থেকে সংখ্যা গড়েছিলে (reverse number/palindrome-এ)। এখানে হুবহু সেই গড়া, শুধু প্রতি ধাপে `% m` যোগ।
মানে নতুন কিছু নয় — চেনা "digit ধরে সংখ্যা বানানো" + চেনা "প্রতি step-এ mod" = বিশাল সংখ্যার mod।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **Horner's method + modular reduction**। একটা decimal সংখ্যা আসলে:
`1234 = ((1 × 10 + 2) × 10 + 3) × 10 + 4`
মানে digit গুলো বাঁ থেকে পড়ে প্রতিবার "আগেরটাকে ×10, তারপর নতুন digit যোগ" — এভাবে সংখ্যাটা গড়ে ওঠে। এখন 027/028-এর নিয়ম: যোগ আর গুণে প্রতি step-এ mod নিরাপদ। তাই প্রতি ধাপে `% m` নিলে:
`r = (r × 10 + digit) % m`
এতে `r` কখনো `10m`-এর বেশি বড় হয় না, অথচ শেষে ঠিক সেই সংখ্যা mod m পাওয়া যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল (Python-এই সম্ভব): পুরো string-কে int বানিয়ে mod।
```python
def big_mod_brute(s, m):
return int(s) % m # পুরো বিশাল সংখ্যা বানিয়ে তারপর mod
```
Python-এ unbounded int বলে ঠিক উত্তর দেয়। কিন্তু এটা ভাষা-নিরপেক্ষ নয় (C++/Java-তে `int(s)` ধরবে না), আর বিশাল string-এ মাঝের সংখ্যা প্রকাণ্ড।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো সমস্যা:
1. **ভাষা-নির্ভরতা:** C++/Java-তে `"123...(10^5 digit)"` কোনো built-in int-এ ধরে না; big-integer library লাগে। interview-তে "string হিসেবে এসেছে" বললেই বোঝায় digit-by-digit চায়।
2. **Python-এও খরচ:** `int(s)` পুরো 10⁵-digit সংখ্যা মেমরিতে বানায়, তারপর সেই দানবকে mod — digit সংখ্যার সাথে কাজ বাড়ে, আর বড় int-এর mod তুলনায় ভারী।
```text
s = 10^5 digit হলে:
brute: 10^5-digit int বানাও (ভারী), তারপর mod
smart: প্রতি digit-এ r = (r*10+d)%m -> r সবসময় ছোট, O(n) সহজ পাস
```
মূল শিক্ষা: পুরো সংখ্যা বানানোর দরকারই নেই — digit ধরে remainder build করো।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
Horner + প্রতি step-এ mod:
```python
def big_mod(s, m):
r = 0
for ch in s:
r = (r * 10 + int(ch)) % m
return r
```
প্রতি digit-এ `r`-কে 10 গুণ করে নতুন digit যোগ, সঙ্গে সঙ্গে `% m`। `r` কখনো `10m`-এর বেশি বড় হয় না, তাই দ্রুত আর overflow-মুক্ত — যেকোনো ভাষায় চলবে।
এটা আসলে 038-এর polynomial hashing-এরও কাঠামো (সেখানে 10-এর বদলে base B)। মনে রেখো — একই হাড়ের কাঠামো বারবার ফিরবে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **পুরো বিশাল সংখ্যা একবারে দেখার দরকার নেই — digit ধরে ধরে remainder গড়ো, প্রতি ধাপে ছোট করে নাও।** Level 0-এ digit থেকে *সংখ্যা* বানিয়েছিলে; এখন digit থেকে সরাসরি *remainder* বানাচ্ছ — মাঝের দানব সংখ্যাটা skip।
ছোট tweak: চাইলে base 10 না হয়ে অন্য কিছুও হতে পারে — string hashing-এ এই একই loop base 31/53 দিয়ে চলে। তাই এই কাঠামোটা শুধু "বড় সংখ্যা mod" নয়, একটা general fingerprint engine।
### ছবিতে বোঝা {#5-visual-explanation}
`"1234" % 7` — digit ধরে এগোনো:
```text
r শুরুতে 0, প্রতি digit-এ: r = (r * 10 + digit) % 7
digit: 1 2 3 4
r: 0 ─> (0*10+1)%7 ─> (1*10+2)%7 ─> (5*10+3)%7 ─> (4*10+4)%7
= 1 = 12%7=5 = 53%7=4 = 44%7=2
^ উত্তর 2
Check: 1234 = 7×176 + 2 -> 1234 % 7 = 2 ✓
```
লক্ষ করো `r` কখনো `7×10 + 9 = 79`-এর বেশি গেল না — সংখ্যা বিশাল হলেও remainder ছোট্ট:
```text
"123456789...(10^5 digit)" % m:
পুরো int বানালে: 10^5 digit-এর দানব সংখ্যা
digit-by-digit: r সবসময় < 10m -> ছোট, প্রতি step O(1)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`big_mod("1234", 7)`:
| step | ch | int(ch) | r (আগে) | r*10 + d | (r*10 + d) % 7 |
| --- | --- | --- | --- | --- | --- |
| শুরু | — | — | 0 | — | 0 |
| 1 | '1' | 1 | 0 | 0×10 + 1 = 1 | 1 % 7 = 1 |
| 2 | '2' | 2 | 1 | 1×10 + 2 = 12 | 12 % 7 = 5 |
| 3 | '3' | 3 | 5 | 5×10 + 3 = 53 | 53 % 7 = 4 |
| 4 | '4' | 4 | 4 | 4×10 + 4 = 44 | 44 % 7 = 2 |
উত্তর **2**। Check: `int("1234") % 7 = 1234 % 7 = 2` ✓। লক্ষ করো মাঝের সবচেয়ে বড় সংখ্যা ছিল 53 — কখনো বড় হলো না, যদিও মূল সংখ্যা 1234।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def big_mod(s, m):
"""বিশাল সংখ্যা s (string) % m — digit ধরে, Horner + প্রতি step mod।"""
r = 0
for ch in s:
r = (r * 10 + int(ch)) % m
return r
def big_mod_signed(s, m):
"""leading '-' সামলে: negative বড় সংখ্যাও non-negative remainder।"""
neg = s[0] == '-'
digits = s[1:] if (neg or s[0] == '+') else s
r = 0
for ch in digits:
r = (r * 10 + int(ch)) % m
return (m - r) % m if neg else r # negative হলে ঘড়িতে উল্টো দিক
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert big_mod("1234", 7) == 2
assert big_mod("100", 9) == 1
assert big_mod("0", 5) == 0
assert big_mod("123456789012345678901", 1000) == 901 # শেষ 3 digit
# brute (int(s) % m) এর সাথে মিলিয়ে দেখা — এটাই মূল যাচাই:
assert big_mod("999999999999", 7) == int("999999999999") % 7
big_str = "123456789012345678901234567890" * 5 # 150 digit
assert big_mod(big_str, 1000000007) == int(big_str) % 1000000007
assert big_mod("98765432109876543210", 13) == int("98765432109876543210") % 13
# negative version:
assert big_mod_signed("-1234", 7) == (-1234) % 7 # Python: 5
assert big_mod_signed("+100", 9) == 1
print(big_mod("1234", 7)) # 2
print(big_mod("123456789012345678901", 1000)) # 901
print(big_mod_signed("-1234", 7)) # 5
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
r = 0
for ch in s:
r = (r * 10 + int(ch)) % m
return r
```
`r` শুরু 0। প্রতিটা character `ch`-কে `int(ch)` দিয়ে digit-এ পরিণত করি; `r * 10` মানে আগের সংখ্যাকে এক ঘর বাঁয়ে সরানো, তাতে নতুন digit যোগ — এটাই Horner। সঙ্গে সঙ্গে `% m` নেওয়ায় `r` ছোট থাকে। loop শেষে `r`-ই পুরো সংখ্যা mod m।
```text
neg = s[0] == '-'
digits = s[1:] if (neg or s[0] == '+') else s
...
return (m - r) % m if neg else r
```
`big_mod_signed`-এ প্রথমে sign খুঁজি, digit অংশ আলাদা করি। positive remainder `r` বের করার পর negative হলে ঘড়িতে উল্টো দিক — `(m - r) % m` দিয়ে non-negative ঘরে আনি। (`% m` বাইরে রাখলাম `r = 0` হলে `m - 0 = m` কে আবার 0 করতে।)
`assert big_mod(...) == int(s) % m` লাইনগুলো Python-এর সরাসরি big-int mod-এর সাথে মিলিয়ে দেখছে — 150-digit সংখ্যাতেও। এটাই নিশ্চিত করে আমাদের digit-by-digit হিসাব নির্ভুল। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2
901
5
সব test pass!
```
প্রথম লাইন `big_mod("1234", 7)` → 2। দ্বিতীয় `big_mod("123...901", 1000)` → 901 (শেষ 3 digit, কারণ mod 1000)। তৃতীয় `big_mod_signed("-1234", 7)` → 5 (Python-এ −1234 % 7 = 5, ঘড়িতে উল্টো দিক)। আগের সব `assert` (150-digit সহ `int(s) % m`-এর সাথে মিল) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — `n` = digit সংখ্যা; প্রতিটা digit-এ একবার O(1) কাজ (একটা গুণ, একটা যোগ, একটা mod)। `int(s) % m` brute-ও মোটামুটি O(n) digit পড়ে, কিন্তু সে আগে পুরো big-int বানায় — constant factor ভারী, আর ভাষা-নির্ভর।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — input string ছাড়া শুধু একটা `r` variable। পুরো big-int কখনো বানাই না, তাই বাড়তি জায়গা প্রায় শূন্য (brute-এ পুরো big-int-এর জন্য O(n) জায়গা লাগে)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **`r * 10` ভুলে `r + 10` বা শুধু digit যোগ** — Horner-এ আগের সংখ্যাকে **10 গুণ** করতে হয় (place value বাড়ানো), শুধু যোগ নয়।
- **প্রতি step-এ mod না নিয়ে শেষে একবার** — তাহলে `r` বিশাল হয়ে যায়; পুরো বড় সংখ্যা বানানোর সমস্যাই ফিরে এল।
- **char-কে সরাসরি ব্যবহার** — `'5'` একটা character, `int('5')` করে digit-এ আনতে হয় (নাহলে TypeError বা ord-এর ভুল মান)।
- **leading sign/space ভুলে যাওয়া** — `"-1234"` বা `" 1234"` এলে sign/whitespace handle না করলে `int(ch)` crash।
- **mod 1 / m = 0** — mod 1 হলে উত্তর 0 (ঠিকই আসে); m = 0 হলে ZeroDivisionError — ধরে নাও m > 0।
- **খালি string** — `""` দিলে loop চলে না, `r = 0` ফেরত; প্রয়োজনে আলাদা handle।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Add Strings** (