074 — Count Subarrays Divisible by K

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

Source

• 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)

1. Problem in simple words

একটা সংখ্যার 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।

2. What is the math idea?

মূল 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 = পার্থক্য বিভাজ্য) এখানে সরাসরি ফসল।

3. Which basic idea does this inherit from?

মূলত 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 তার পোশাক-বদল মাত্র।

4. Real-life analogy

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

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

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

5. Visual explanation

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 লাগত। এই অভ্যাসটা মনে রাখো।

6. Example input and 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 স্বাভাবিকভাবেই সামলায়।

7. Brute force thinking

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

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 বাড়ায়।

8. Why brute force may be slow

দুটো 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 এসেছে" সরাসরি জানা যায়।

9. Better thinking

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

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।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: বিভাজ্যতা = একই 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।

11. Step-by-step dry run

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 আসত।)

12. Python solution

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!")

13. Line-by-line explanation

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

14. Output walkthrough

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!

15. Time complexity

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

16. Space complexity

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

17. Common mistakes

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 ধরো।

18. Harder problems that inherit this idea

• 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 শর্ত সহ)।

19. Pattern learned

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 করো।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "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" লেখো।