074 — Count Subarrays Divisible by K

073-এর hash চালটাই এখানে নতুন পোশাকে ফেরে। সেখানে খুঁজতাম "sum ঠিক K", এখানে "sum K দিয়ে ভাগ যায়"। চাবিটা একই রকম সুন্দর: দুটো prefix-এর remainder এক হলেই মাঝের অংশ K দিয়ে বিভাজ্য। Level 2-এর mod-চিন্তা এখানে ফসল দেবে। ধীরে পড়ো — negative number-এ remainder normalize করার অভ্যাসটা গেঁথে নাও।

Problem link ও উৎস

• Original source: Classic technique (prefix mod + hash map)
• Platform: LeetCode Subarray Sums Divisible by K — https://leetcode.com/problems/subarray-sums-divisible-by-k/, CSES Subarray Divisibility — https://cses.fi/problemset/task/1662
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Medium
• Pattern: prefix sum mod K + hash map (same-remainder counting)
• Basic idea inherited from: 073 — Subarray Sum Equals K (এবং Level 2-এর 026 — modular arithmetic)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা সংখ্যার array a (negative-ও থাকতে পারে) আর একটা ধনাত্মক সংখ্যা K দেওয়া। তোমাকে গুনতে হবে — কতগুলো contiguous subarray আছে যাদের sum K দিয়ে নিঃশেষে ভাগ যায় (অর্থাৎ sum % K == 0)?

073-এর মতোই, শুধু শর্তটা "sum ঠিক K" থেকে বদলে "sum, K দিয়ে বিভাজ্য"। যেমন a = [4, 5, 0, -2, -3, 1], K = 5 হলে উত্তর 7।

Input ও output

উদাহরণ

a                       K   -> count
-----------------------------------------------
[4, 5, 0, -2, -3, 1]    5   -> 7        (LeetCode classic)
[5]                     9   -> 0        একটাই element, বিভাজ্য নয়
[2, -2, 2, -4]          6   -> 2
[1, 2, 3, 4, 5]         3   -> 7
[-1, 2, 9]              2   -> 2

Edge case: negative সংখ্যা ([4,5,0,-2,-3,1]) — remainder normalize করতে হয় (Python এমনিতেই করে)। আর 0-ও একটা element হতে পারে — তার remainder 0, hash map স্বাভাবিকভাবেই সামলায়।

চেনা উদাহরণে বোঝা

ভাবো একটা বৃত্তাকার ঘড়ির ডায়াল যাতে K ঘর (যেমন 5 ঘরের ঘড়ি)। তুমি হাঁটছ আর প্রতিবার যোগফল অনুযায়ী কাঁটা ঘুরছে — কিন্তু K ঘরের পর আবার শুরুতে ফিরে আসছে (mod K)।

তুমি জানতে চাও — কোন কোন অংশে হাঁটার পর কাঁটা ঠিক একই জায়গায় ফিরে এসেছে? কারণ কাঁটা একই জায়গায় ফিরলে মানে মাঝের হাঁটাটা ঠিক K-এর গুণিতক — পুরো পাক!

তাই তুমি লিখে রাখো প্রতিটা ঘর-অবস্থানে (remainder) কতবার কাঁটা ছিল। একই অবস্থানে দুবার থাকা মানেই একটা বিভাজ্য অংশ। নোটবুকে (hash map) প্রতি অবস্থানের count রাখো, প্রতিবার "এই অবস্থানে আগে কতবার ছিলাম" যোগ করো।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূলত 073 (Subarray Sum Equals K) থেকে — হুবহু একই hash map কাঠামো। আর Level 2-এর 026 (modular arithmetic) থেকে remainder-এর ধর্ম।

073-এ key ছিল prefix sum-এর মান, খুঁজতাম P - K। এখানে key হলো prefix sum-এর remainder (P % K), আর খুঁজি একই remainder। কাঠামো প্রায় copy — শুধু "P-K কতবার" এর জায়গায় "P % K কতবার", আর seen[0] = 1 একই কারণে থাকে। এই কারণেই 073 আগে শেখা দরকার — 074 তার পোশাক-বদল মাত্র।

ভেতরের অঙ্ক

মূল idea হলো prefix sum mod K + একই remainder-এর জোড়া গোনা।

subarray (l..r)-এর sum = P[r] - P[l-1]। এটা K দিয়ে বিভাজ্য মানে:

উদাহরণ

(P[r] - P[l-1]) % K == 0   ⟺   P[r] % K == P[l-1] % K

মানে: একই remainder-ওয়ালা দুটো prefix = একটা valid subarray। তাই প্রতিটা remainder কতবার এসেছে গোনো; কোনো remainder যদি c বার আসে, সেগুলো থেকে c·(c-1)/2 টা জোড়া বানানো যায় (অথবা চলার পথে প্রতিবার আগের count যোগ করলেই হয়)। গোনার যন্ত্র সেই hash map। Level 2-এর mod-চিন্তা (একই remainder = পার্থক্য বিভাজ্য) এখানে সরাসরি ফসল।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সব (l, r) জোড়ার subarray-র sum বের করে % K == 0 চেক:

Python

def count_div_k_brute(a, K):
    n = len(a)
    count = 0
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]
            if s % K == 0:
                count += 1
    return count

সরল, ঠিক উত্তর — প্রতিটা শুরু l-এর জন্য r বাড়িয়ে running sum, বিভাজ্য হলে count বাড়ায়।

কোথায় বেশি কাজ হতে পারে

দুটো nested loop, প্রায় n²/2 subarray — O(n²)।

উদাহরণ

n = 30000 হলে:
  brute force: ~4.5 × 10^8 operation  (O(n²)) — TLE
  hash way   : ~30000 operation       (এক pass, O(n))

073-এর মতোই অপচয়: প্রতিটা l-এর জন্য আবার ডান দিকে হাঁটা। অথচ remainder-এর frequency রাখলে "কতবার আগে একই remainder এসেছে" সরাসরি জানা যায়।

আরও ভালোভাবে ভাবা

মূল insight: (P[r] - P[l-1]) % K == 0 মানে P[r] % K == P[l-1] % K। তাই প্রতিটা remainder-এর frequency hash map-এ রাখি; প্রতি r-এ "আমার remainder আগে কতবার এসেছে" যোগ করি:

Python

def count_div_k(a, K):
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1                  # খালি prefix (remainder 0) — শুরু থেকে বিভাজ্য subarray-র জন্য
    P = 0
    count = 0
    for x in a:
        P = (P + x) % K          # remainder, Python-এ negative-ও [0, K)
        count += seen[P]         # একই remainder আগে যতবার = তত valid subarray
        seen[P] += 1
    return count

এক pass, প্রতি step O(1) — মোট O(n)। 073-এর প্রায় হুবহু code, শুধু key = P % K, আর খুঁজি একই remainder।

ভাবনার পরিবর্তন

আসল "আহা!" মুহূর্ত: বিভাজ্যতা = একই remainder। sum বিভাজ্য কিনা সরাসরি না দেখে, দুটো prefix-এর remainder মেলানো — P[r] % K == P[l-1] % K। এটাই Level 2-এর "একই remainder মানে পার্থক্য বিভাজ্য" ধর্মের সরাসরি প্রয়োগ।

দ্বিতীয় tweak (ভাষা-নির্ভর ফাঁদ): negative-এ remainder normalize করো। Python-এ (P + x) % K এমনিতেই [0, K)-তে থাকে (সুবিধা!), কিন্তু C++/Java-তে negative আসে — তখন ((P % K) + K) % K লাগে। এই অভ্যাসটা না থাকলে অন্য ভাষায় চুপচাপ ভুল answer।

ছবিতে বোঝা

a = [2, -2, 2, -4], K = 6। running prefix-এর remainder P % K, hash map seen (শুরুতে {0: 1})। Python-এ % সবসময় [0, K)-তে remainder দেয়, negative-এও:

উদাহরণ

শুরু:  seen = {0: 1},  P = 0,  count = 0

x = 2:   P = (0 + 2) % 6 = 2
         এই remainder আগে? seen[2] = 0 → count += 0।  seen = {0:1, 2:1}

x = -2:  P = (2 + (-2)) % 6 = 0
         এই remainder আগে? seen[0] = 1 → count += 1 = 1।  seen = {0:2, 2:1}
         (remainder 0 আবার এল → শুরু থেকে এ পর্যন্ত sum বিভাজ্য: 2-2=0 ✓)

x = 2:   P = (0 + 2) % 6 = 2
         seen[2] = 1 → count += 1 = 2।  seen = {0:2, 2:2}
         (remainder 2 আবার → মাঝের অংশ -2+2=0 বিভাজ্য ✓)

x = -4:  P = (2 + (-4)) % 6 = (-2) % 6 = 4    ← Python: negative-ও [0,6)-তে
         seen[4] = 0 → count += 0 = 2।  seen = {0:2, 2:2, 4:1}

উত্তর: count = 2

মূল কথা: একই remainder-এ ফিরে আসা = বিভাজ্য subarray। (-2) % 6 = 4 — Python নিজেই normalize করে, কিন্তু C++/Java-তে এটা −2 আসত, তাই সেখানে ((P % K) + K) % K লাগত। এই অভ্যাসটা মনে রাখো।

ছোট input-এ ধাপে ধাপে

a = [-1, 2, 9], K = 2। শুরুতে seen = {0: 1}, P = 0, count = 0:

x	P = (P+x) % K	seen[P] (যোগ)	count	seen আপডেট
-1	(0-1) % 2 = 1	0	0	{0:1, 1:1}
2	(1+2) % 2 = 1	1	1	{0:1, 1:2}
9	(1+9) % 2 = 0	1	2	{0:2, 1:2}

শেষ অবস্থা: count = 2। দুটো বিভাজ্য subarray: [2] (sum 2 — index 0 আর index 1-এ remainder একই 1, তাই মাঝের [2] বিভাজ্য) আর [-1, 2, 9] (sum 10 — index 2-এ remainder 0 আবার এল, খালি prefix-এর সাথে মিলে পুরো array বিভাজ্য)। brute force-ও 2 দেয় ✓। ((0-1) % 2 = 1 — Python নিজেই normalize করে, C++-এ −1 আসত।)

কোড ও ব্যাখ্যা

Python

Python

from collections import defaultdict


def count_div_k(a, K):
    """sum K দিয়ে বিভাজ্য এমন contiguous subarray-র সংখ্যা; prefix mod + hash map, O(n)।"""
    seen = defaultdict(int)
    seen[0] = 1                  # খালি prefix, remainder 0
    P = 0
    count = 0
    for x in a:
        P = (P + x) % K          # Python: negative-ও [0, K)-তে normalize হয়
        count += seen[P]         # একই remainder আগে যতবার = তত নতুন subarray
        seen[P] += 1
    return count


def count_div_k_brute(a, K):
    """ধীর O(n^2) version — মিলিয়ে দেখার জন্য।"""
    n = len(a)
    count = 0
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += a[r]
            if s % K == 0:
                count += 1
    return count


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_div_k([4, 5, 0, -2, -3, 1], 5) == 7   # LeetCode classic
assert count_div_k([5], 9) == 0
assert count_div_k([2, -2, 2, -4], 6) == 2
assert count_div_k([1, 2, 3, 4, 5], 3) == 7
assert count_div_k([-1, 2, 9], 2) == 2

# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(19)
for _ in range(500):
    arr = [random.randint(-5, 5) for _ in range(random.randint(0, 10))]
    K = random.randint(1, 7)
    assert count_div_k(arr, K) == count_div_k_brute(arr, K)

print(count_div_k([4, 5, 0, -2, -3, 1], 5))   # 7
print(count_div_k([1, 2, 3, 4, 5], 3))        # 7
print("সব test pass!")

কোডের প্রতিটি অংশ

উদাহরণ

seen = defaultdict(int)
seen[0] = 1

hash map (key = remainder, value = কতবার)। seen[0] = 1 মানে "খালি prefix-এর remainder 0 একবার দেখেছি" — শুরু থেকে বিভাজ্য subarray গোনার জন্য।

উদাহরণ

P = (P + x) % K

running prefix-এর remainder। Python-এ % সবসময় [0, K) দেয়, তাই negative x-এও remainder ঠিক থাকে — আলাদা normalize লাগে না (অন্য ভাষায় লাগত)।

উদাহরণ

count += seen[P]
seen[P] += 1

এই remainder আগে যতবার এসেছে (seen[P]), ততগুলো নতুন বিভাজ্য subarray এখানে শেষ হচ্ছে — যোগ করলাম। তারপর নিজের remainder জমালাম। ক্রম: আগে খোঁজো, পরে লেখো।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random array-তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check)। সব মিললে সব test pass!।

Output মিলিয়ে দেখা

a = [4, 5, 0, -2, -3, 1], K = 5:

• remainder চলতে চলতে একই remainder বারবার ফিরে আসে; প্রতিবার আগের count যোগ হয়
• মোট হিসাবে count = 7 → প্রথম print ছাপে 7
• count_div_k([1,2,3,4,5], 3) → 7 → দ্বিতীয় print ছাপে 7
• সব assert pass → সব test pass!

ছাপা output:

উদাহরণ

7
7
সব test pass!

খরচ ও সাধারণ ভুল

সময়

O(n) — array-র উপর এক pass, প্রতি element-এ একটা hash lookup + insert (গড়ে O(1))। brute force-এর O(n²) থেকে বিশাল উন্নতি।

অতিরিক্ত জায়গা

O(K) — hash map-এ remainder মাত্র K রকম (0 থেকে K-1), তাই entry সর্বোচ্চ K। 073-এর O(n)-এর চেয়েও কম, কারণ এখানে key বদ্ধ পরিসরে।

যে ভুলগুলো এড়াতে হবে

1. negative remainder normalize না করা — Python সামলায়, কিন্তু C++/Java-তে -2 % 5 = -2; তখন ((P % K) + K) % K লাগে, নইলে key ভুল।
2. seen[0] = 1 ভুলে যাওয়া — শুরু থেকে বিভাজ্য subarray গোনা হয় না (073-এর মতোই #1 bug)।
3. key হিসেবে raw prefix sum রাখা (remainder নয়) — তখন divisibility ধরা পড়ে না; key অবশ্যই P % K।
4. খোঁজা-লেখার ক্রম উল্টানো — আগে count += seen[P], পরে seen[P] += 1; উল্টালে নিজের remainder নিজেকে গুনে বেশি আসে।
5. K = 0 ধরে নেওয়া — divisibility-তে K ধনাত্মক হতে হয়; % 0 error। প্রশ্নে K ≥ 1 ধরো।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

• LeetCode — Subarray Sums Divisible by K (https://leetcode.com/problems/subarray-sums-divisible-by-k/) — ঠিক এই problem।
• CSES — Subarray Divisibility (https://cses.fi/problemset/task/1662) — একই কৌশল, বড় input।
• LeetCode — Continuous Subarray Sum (https://leetcode.com/problems/continuous-subarray-sum/) — prefix mod + hash map-এর আরেক রূপ (length শর্ত সহ)।

কৌশলটি মনে রাখুন

Prefix mod + hash map (same-remainder counting) — key = P % K, একই remainder-এর জোড়া = বিভাজ্য subarray; seen[0] = 1 দিয়ে শুরু। বড় শিক্ষা: বিভাজ্যতা = একই remainder; 073-এর hash চালটাই key বদলে (P-K → P % K) এখানে ফেরে। negative-এ remainder normalize করো।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "divisible-by-K গোনা = prefix mod + hash map; key = P % K, প্রতি step count += seen[P]; seen[P] += 1, শুরুতে seen[0] = 1। একই remainder = বিভাজ্য। negative হলে normalize (Python এমনিতেই করে)।"

পরের ধাপ → 075 — Contribution Technique Basic (দৃষ্টিভঙ্গি উল্টাও: subarray না গুনে element গোনো)।

ফিরে দেখা: শিকড় → 073 — Subarray Sum Equals K · Level 2-এর mod → ../../02-modular-arithmetic/ · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

---

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