031 — Large Number Mod

ধরো সংখ্যাটা এত বড় যে এক লাইনে লেখাই কঠিন — file থেকে আসছে 10⁵ digit-এর একটা string হয়ে। পুরোটা int বানিয়ে mod নেওয়া যায়, কিন্তু আছে আরও সুন্দর, ভাষা-নিরপেক্ষ একটা উপায়: Level 0-এর digit loop + 027-এর "প্রতি step-এ mod"। এই দুই পুরনো বন্ধু আজ হাত মেলাবে।

Source

• 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

1. Problem in simple words

একটা বিশাল সংখ্যা string হিসেবে দেওয়া (যেমন "123456789012345678901234567890") আর একটা ছোট m। বের করতে হবে সেই বিশাল সংখ্যা % m।

কেন string? কারণ সংখ্যাটা এত বড় যে অনেক ভাষায় (C++/Java) কোনো int type-এই ধরে না। Python-এ ধরে, কিন্তু আমরা একটা ভাষা-নিরপেক্ষ, দ্রুত উপায় শিখব — যেটা সংখ্যাকে কখনো পুরো বড় হতে দেয় না।

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 পাওয়া যায়।

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।

4. Real-life analogy

ভাবো একটা odometer (গাড়ির মাইল-মিটার) যেটা শুধু 0 থেকে m−1 পর্যন্ত গুনতে পারে, তারপর আবার 0-তে ফেরে। তুমি একটা বিশাল দূরত্ব digit ধরে ধরে ঢোকাচ্ছ।

প্রতিবার একটা নতুন digit ঢোকানো মানে: আগের পুরো সংখ্যাকে 10 গুণ করে (এক ঘর বাঁয়ে সরিয়ে) নতুন digit যোগ। কিন্তু odometer-টা ছোট — তাই প্রতিবার সে নিজে নিজে চক্কর ফেলে শুধু "শেষ অবস্থান" রাখে (% m)। শেষ digit ঢোকানো হলে odometer-এ যা দেখাচ্ছে সেটাই পুরো সংখ্যা mod m। সে কখনো বিশাল সংখ্যাটা মনে রাখেনি — শুধু ছোট remainder।

5. Visual explanation

"1234" % 7 — digit ধরে এগোনো:

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 ছোট্ট:

"123456789...(10^5 digit)" % m:
  পুরো int বানালে: 10^5 digit-এর দানব সংখ্যা
  digit-by-digit:  r সবসময় < 10m  ->  ছোট, প্রতি step O(1)

6. Example input and output

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 এটা আপনাআপনি বের করে।

7. Brute force thinking

সবচেয়ে সরল (Python-এই সম্ভব): পুরো string-কে int বানিয়ে mod।

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 তুলনায় ভারী।

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:

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।

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।

12. Python solution

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

    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।

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

14. Output walkthrough

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

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

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।

18. Harder problems that inherit this idea

• LeetCode — Add Strings (https://leetcode.com/problems/add-strings/) আর Multiply Strings (https://leetcode.com/problems/multiply-strings/) — string হিসেবে বিশাল সংখ্যার যোগ/গুণ; একই "digit ধরে কাজ" দর্শন।
• 038 (Hashing with Mod) (https://cp-algorithms.com/string/string-hashing.html) — হুবহু এই loop, শুধু base 10-এর বদলে 31/53 আর char-এর ord; fingerprint বানানো।
• HackerRank / CSES বড় সংখ্যা mod problems — যেখানে input-ই 10⁶ digit-এর; digit-by-digit ছাড়া উপায় নেই।

19. Pattern learned

Digit-by-digit modulo (Horner + mod) — বিশাল সংখ্যা string হলে r = (r * 10 + digit) % m দিয়ে প্রতি digit-এ remainder build করো; পুরো int কখনো বানিও না। base 10-কে B করলে এটাই string hashing।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "বিশাল সংখ্যা mod = r = (r*10 + digit) % m প্রতি digit-এ; পুরো সংখ্যা বানানোর দরকার নেই। 'সংখ্যা string হিসেবে এসেছে / অনেক বড়' — এই signal দেখলেই digit-by-digit; base বদলালে এটাই hashing।"

পরের ধাপ → 032 — Modular Inverse Basic (mod-জগতে ভাগের বদলি)। সম্পর্কিত → 026 — Remainder Basics, 038 — Hashing with Mod।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" / "CP-তে নিত্য দরকারি" লেখা।