027 — Modular Addition¶

026-এ ঘড়ির ছবিটা মাথায় বসিয়েছ — এখন সেই ঘড়িতে যোগ করব। মূল আবিষ্কার: ঘড়ির জগতে যোগ করার সময় বড় সংখ্যা পুরো রাখার দরকার নেই; প্রতি step-এ ছোট করে নিলেও উত্তর একই থাকে। এই অভ্যাসটাই পরের প্রতিটা problem-এ ফিরবে।

Source¶

Original source: Classic exercise (modular arithmetic-এর যোগের নিয়ম)
Platform: Classic exercise — প্রায় সব CP intro আর textbook-এ থাকে
Topic: Math-based programming fundamentals → Level 2: Modular Arithmetic
Difficulty: Easy
Pattern: (a+b)%m (modular addition / subtraction)
Basic idea inherited from: 026 — Remainder Basics (clock model + remainder)

1. Problem in simple words¶

দুটো (বা অনেকগুলো) integer আর একটা m দেওয়া। বলতে হবে তাদের যোগফল mod m — মানে (a + b) % m।

আসল challenge: a আর b এত বড় হতে পারে যে যোগফল রাখা কঠিন/ধীর (C++/Java-তে overflow, Python-এ বিশাল সংখ্যা slow)। তাই আমরা চাই — পুরো যোগফল না বানিয়ে, প্রতি step-এ m-এর ঘড়িতে নামিয়ে নিয়ে কাজ করতে।

আর বিয়োগ: (a − b) % m — যেটা negative হয়ে যেতে পারে, সেটাকে non-negative রাখা।

2. What is the math idea?¶

মূল idea — modular addition rule:

(a + b) % m = ((a % m) + (b % m)) % m

মানে যোগের আগে দুজনকে আলাদা আলাদা ঘড়ির ঘরে নামিয়ে নিলেও শেষ উত্তর একই।

কেন? a = q₁m + r₁, b = q₂m + r₂ লিখলে a + b = (q₁+q₂)m + (r₁+r₂)। এখানে (q₁+q₂)m অংশটা m-এর গুণিতক — ঘড়িতে পুরো পুরো চক্কর, কাঁটার অবস্থানে কোনো প্রভাব নেই। কাঁটা কোথায় থামবে তা ঠিক করে শুধু (r₁ + r₂)।

বিয়োগেও একই: (a − b) % m = ((a % m) − (b % m)) % m, তবে এখানে ফল negative হতে পারে।

3. Which basic idea does this inherit from?¶

সরাসরি 026 — Remainder Basics থেকে। 026-এ শিখেছ একটা সংখ্যাকে ঘড়ির ঘরে নামানো (a % m)। এখন দুটো সংখ্যাকে নামিয়ে যোগ করা।

026-এর ((a % m) + m) % m (negative-safe রূপ) এখানে সরাসরি কাজে আসবে বিয়োগের বেলায়। মানে remainder-এর basic বোঝাপড়াটাই এখানে দুই-অপারেন্ডে বিস্তৃত হলো।

আর শিকড়ে ফিরলে — 001-এর % 2 ছিল এক সংখ্যার parity; 026 generalize করল; 027 তাতে যোগ যোগ করল।

4. Real-life analogy¶

আবার সেই 12 ঘণ্টার ঘড়ি। এখন 9টা বাজে, তুমি আরও 8 ঘণ্টা যোগ করবে। 9 + 8 = 17 — কিন্তু ঘড়ি বলে 5টা (17 % 12 = 5)।

এখন ধরো তুমি 9 আর 8 আগেই ঘড়ির হিসাবে ভেবে নিলে: 9 তো ঘড়িতেই 9, 8-ও 8। যোগ করলে 17, আবার ঘড়িতে নামালে 5 — একই উত্তর। বড় সংখ্যা হলেও — যেমন 100 + 50 ঘণ্টা: 100 % 12 = 4, 50 % 12 = 2, (4 + 2) % 12 = 6; আর সরাসরি 150 % 12 = 6। মিলে গেল! এই "আগে ছোট করে নাও" চালাকিই modular addition।

5. Visual explanation¶

m = 12 ধরে, যোগের আগে-পরে mod নেওয়া একই ফল দেয় তা দেখি:

(100 + 50) % 12 দুই রাস্তায়:

রাস্তা A (সরাসরি):  100 + 50 = 150  ->  150 % 12 = 6
রাস্তা B (প্রতি step):
        100 % 12 = 4
         50 % 12 = 2
        (4 + 2) % 12 = 6
                       ^ একই উত্তর! কিন্তু সংখ্যা কখনো 6+11=17 ছাড়াল না

বিয়োগে negative সামলানোর ছবি ((3 - 5) % 12):

3 - 5 = -2   ->  Python: -2 % 12 = 10  (ঘড়িতে 3 থেকে 5 ঘর পিছালে 10)

ভাষা-নিরপেক্ষ safe রূপ:
   ((3 - 5) % 12 + 12) % 12 = (-2 + 12) % 12 = 10 % 12 = 10
   কখনো negative ঘরে যায়নি

6. Example input and output¶

a       b      m   ->  (a+b)%m      ব্যাখ্যা
-----------------------------------------------------
9       8      12  ->  5            17 % 12 = 5
100     50     12  ->  6            150 % 12 = 6
7       3      5   ->  0            10 % 5 = 0
999999  999999 7   ->  2            (চাইলে নিজে মিলাও)

বিয়োগ:

a       b      m   ->  (a-b)%m (non-negative)
-----------------------------------------------------
3       5      12  ->  10           -2 -> 10
5       3      12  ->  2            2 -> 2
0       1      5   ->  4            -1 -> 4

খেয়াল করো বিয়োগে উত্তর negative হতে পারে — আমরা সবসময় 0 থেকে m−1-এ টেনে আনি।

7. Brute force thinking¶

সবচেয়ে সরল: পুরো যোগফল বানিয়ে শেষে একবার mod নাও।

def add_mod_brute(a, b, m):
    total = a + b           # পুরো যোগফল — যত বড়ই হোক
    return total % m

অনেকগুলো সংখ্যা হলে সবগুলো যোগ করে শেষে একবার mod:

def sum_mod_brute(nums, m):
    return sum(nums) % m    # আগে পুরো sum, তারপর mod

Python-এ এটা ঠিক উত্তর দেয় (unbounded int)। কিন্তু এখানেই সমস্যার বীজ।

8. Why brute force may be slow¶

দুটো আলাদা সমস্যা:

C++/Java-তে overflow: a + b যদি 64-bit সীমা (~9.2×10¹⁸) ছাড়ায়, যোগফল wrap করে garbage হয় — তারপর mod নিলেও ভুল উত্তর।
Python-এ slowness: int unbounded, overflow নেই — কিন্তু লক্ষ লক্ষ বিশাল সংখ্যা যোগ করলে মাঝের সংখ্যাগুলো প্রকাণ্ড হয়ে যায়, প্রতিটা যোগ ক্রমশ ধীর।

1000টা সংখ্যা, প্রতিটা ~10^18:
  brute:  sum আগে -> মাঝের total ~10^21, বড় সংখ্যার যোগ ধীর
  smart:  প্রতি যোগের পরেই % m -> সংখ্যা কখনো 2m ছাড়ায় না, দ্রুত

মূল শিক্ষা: বড় হওয়ার সুযোগই দিও না — প্রতি step-এ ছোট করে রাখো।

9. Better thinking¶

modular addition rule কাজে লাগাই — প্রতি যোগের পরেই mod:

def add_mod(a, b, m):
    return ((a % m) + (b % m)) % m

list-এর জন্য প্রতি step-এ mod নিয়ে জমাও:

def sum_mod(nums, m):
    total = 0
    for x in nums:
        total = (total + x) % m     # প্রতি step-এ ঘড়িতে নামাও
    return total

এখন total কখনো 2m-এর বেশি বড় হয় না — ছোট, দ্রুত, overflow-মুক্ত।

বিয়োগে negative-safe রূপ:

def sub_mod(a, b, m):
    return ((a % m) - (b % m) + m) % m

10. Thinking tweak¶

আসল "আহা!": সংখ্যা বড় হওয়ার অপেক্ষা কোরো না — প্রতিটা যোগের পরপরই % m নাও। তাতে মাঝের কোনো সংখ্যাই m-এর ধারেকাছের বেশি বড় হয় না।

আর বিয়োগের tweak: বিয়োগে ফল negative হতে পারে, তাই % m করার আগে + m যোগ করে নাও — (... + m) % m। এই "+m তারপর %m" রূপটা পুরো Level 2-এ negative সামলানোর মন্ত্র।

11. Step-by-step dry run¶

nums = [9, 8, 7], m = 5 — প্রতি step-এ mod:

step	x	total (আগে)	total + x	(total + x) % 5
শুরু	—	0	—	0
1	9	0	9	9 % 5 = 4
2	8	4	12	12 % 5 = 2
3	7	2	9	9 % 5 = 4

উত্তর 4। Check সরাসরি: 9 + 8 + 7 = 24, 24 % 5 = 4 ✓। লক্ষ করো — total কখনো 12-এর বেশি গেল না, যদিও সরাসরি যোগে 24 হতো।

বিয়োগ dry run (3 - 5) % 5:

3 % 5 = 3,  5 % 5 = 0
(3 - 0 + 5) % 5 = 8 % 5 = 3
Check: 3 - 5 = -2, -2 % 5 = 3 ✓

12. Python solution¶

def add_mod(a, b, m):
    """(a + b) % m — প্রতি অপারেন্ড আগে ঘড়িতে নামিয়ে।"""
    return ((a % m) + (b % m)) % m


def sub_mod(a, b, m):
    """(a - b) % m — non-negative রাখতে + m।"""
    return ((a % m) - (b % m) + m) % m


def sum_mod(nums, m):
    """list-এর সব সংখ্যার যোগফল mod m — প্রতি step-এ mod।"""
    total = 0
    for x in nums:
        total = (total + x) % m
    return total


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert add_mod(9, 8, 12) == 5            # 17 % 12
assert add_mod(100, 50, 12) == 6         # 150 % 12
assert add_mod(7, 3, 5) == 0             # 10 % 5

# brute-এর সাথে মিলিয়ে দেখা (যাচাই):
assert add_mod(999999, 999999, 7) == (999999 + 999999) % 7

assert sub_mod(3, 5, 12) == 10           # -2 -> 10
assert sub_mod(5, 3, 12) == 2
assert sub_mod(0, 1, 5) == 4             # -1 -> 4
assert sub_mod(3, 5, 12) == (3 - 5) % 12 # Python-এর সাথে মিল

assert sum_mod([9, 8, 7], 5) == 4        # 24 % 5
assert sum_mod([10**18, 10**18, 10**18], 7) == (3 * 10**18) % 7

print(add_mod(9, 8, 12))     # 5
print(sub_mod(3, 5, 12))     # 10
print(sum_mod([9, 8, 7], 5)) # 4
print("সব test pass!")

13. Line-by-line explanation¶

def add_mod(a, b, m):
    return ((a % m) + (b % m)) % m

দুজনকে আগে আলাদা করে ঘড়িতে নামাই (a % m, b % m), যোগ করি, তারপর আবার % m। এতে মাঝের যোগফল কখনো 2m-এর বেশি বড় হয় না।

def sub_mod(a, b, m):
    return ((a % m) - (b % m) + m) % m

বিয়োগে ফল negative হতে পারে, তাই + m করে non-negative ঘরে টেনে আনি, তারপর % m। এটাই 026-এর negative-safe idea-র যোগ-বিয়োগ রূপ।

def sum_mod(nums, m):
    total = 0
    for x in nums:
        total = (total + x) % m
    return total

total-এ প্রতিটা সংখ্যা যোগ করি, কিন্তু প্রতি step-এই % m। তাই total কখনো বড় হয় না — দ্রুত আর overflow-মুক্ত।

assert ... == (999999 + 999999) % 7 লাইনগুলো brute force-এর সরাসরি যোগের সাথে মিলিয়ে দেখছে — mod-এর bug চোখে দেখা যায় না, এই মেলানোতেই ধরা পড়ে। সব ঠিক থাকলে শেষে সব test pass!।

14. Output walkthrough¶

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

5
10
4
সব test pass!

প্রথম লাইন add_mod(9, 8, 12) → 5 (17 mod 12)। দ্বিতীয় sub_mod(3, 5, 12) → 10 (−2 কে non-negative করে)। তৃতীয় sum_mod([9,8,7], 5) → 4 (24 mod 5)। আগের সব assert চুপচাপ pass করেছে — তারপর সব test pass!।

15. Time complexity¶

add_mod, sub_mod: O(1) — গুটিকয় mod আর যোগ।
sum_mod: O(n) — n টা সংখ্যার উপর একবার করে loop, প্রতিবার O(1) কাজ।

brute force-এর তুলনায় Big-O একই (sum-ও O(n)), কিন্তু এখানে মাঝের সংখ্যা ছোট থাকায় constant factor অনেক কম আর overflow-নিরাপদ।

16. Space complexity¶

O(1) — input list ছাড়া শুধু একটা total variable। বাড়তি list/array লাগছে না।

17. Common mistakes¶

শেষে একবারে mod নেওয়া — sum(nums) % m Python-এ ঠিক উত্তর দেয় কিন্তু মাঝের সংখ্যা বিশাল হয়ে slow; C++/Java হলে overflow-এ ভুল। অভ্যাস: প্রতি যোগের পরেই % m।
বিয়োগে negative ভুলে যাওয়া — (a - b) % m C++-এ negative দিতে পারে; safe রূপ ((a - b) % m + m) % m।
+ m ভুল জায়গায় — বিয়োগে + m করতে হবে % m-এর আগে: ((a - b) + m) % m, ((a - b) % m) + m নয় (পরেরটা m-এর বেশি দিতে পারে যদি মাঝে আবার mod না নাও)।
mod 1 ভুলে যাওয়া — সব কিছু mod 1 = 0; যোগফলও 0 হওয়া উচিত।
operand আগে mod না নিয়ে বিশাল রাখা — a নিজেই বিশাল হলে (a % m) আগে নিলে নিরাপদ; সরাসরি a + b রাখলে C++-এ overflow।

18. Harder problems that inherit this idea¶

CSES — Exponentiation (https://cses.fi/problemset/task/1095) — power-এর ভেতরের গুণেও "প্রতি step-এ mod" এই একই দর্শন; যোগ থেকে গুণে গিয়ে।
028 (Modular Multiplication) — পরের সরাসরি ধাপ: যোগের নিয়মটাই গুণে।
034 (nCr mod Prime) — সেখানে যোগ/গুণ/inverse সব মিলে; "প্রতি step-এ mod" না জানলে সেটা অচল।

19. Pattern learned¶

Mod at every step (addition/subtraction) — (a + b) % m = ((a%m) + (b%m)) % m; list-এ প্রতি যোগের পরেই % m। বিয়োগে negative সামলাতে (... + m) % m। বড় সংখ্যা পুরো রাখার বদলে প্রতি step-এ ছোট করে নাও।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "যোগে/বিয়োগে প্রতি step-এ % m নাও — মাঝের সংখ্যা কখনো বড় হতে দিও না; বিয়োগে negative এড়াতে + m তারপর % m। এটাই overflow আর slowness দুটোরই দাওয়াই।"

পরের ধাপ → 028 — Modular Multiplication (একই নিয়ম গুণে)। সম্পর্কিত → 026 — Remainder Basics, 031 — Large Number 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-তে নিত্য দরকারি" লেখা।