014 — Continuous Subarray Sum¶

Problem link ও উৎস

Original source: Classic prefix-mod + hash map exercise
Platform: LeetCode — https://leetcode.com/problems/continuous-subarray-sum/
Topic: prefix sum + hash map (mod)
Difficulty: Medium
Pattern: prefix sum + hash map (mod)
Basic idea inherited from: Subarray Sum Equals K — prefix-এর বদলে remainder জমা রাখো

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

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

একটা অঋণাত্মক সংখ্যার array nums আর একটা সংখ্যা k দেওয়া আছে। বলতে হবে: এমন কোনো contiguous subarray আছে কি, যার দৈর্ঘ্য অন্তত 2 আর যোগফল k-এর একটা গুণিতক (অর্থাৎ 0, k, 2k, 3k, ...)? উত্তর True/False।

উদাহরণ

nums = [23, 2, 4, 6, 7], k = 6
[2, 4]-এর যোগ 6 = 6 × 1 → হ্যাঁ
উত্তর: True

Input ও output¶

উদাহরণ

Input : [23, 2, 4, 6, 7], k = 6     Output: True    ([2,4] = 6)
Input : [23, 2, 6, 4, 7], k = 6     Output: True    (পুরোটা 42 = 6×7)
Input : [23, 2, 6, 4, 7], k = 13    Output: False
Edge  : [0, 0], k = 1               Output: True    ([0,0] = 0 = 0×1)
Edge  : [1, 0], k = 2               Output: False   (length-2 যোগ 1, গুণিতক নয়)

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

ভাবো একটা গোল ঘড়ির ডায়াল, ঘর সংখ্যা k। তুমি হাঁটছ আর প্রতিটা ধাপে কাঁটা কিছু ঘর এগোচ্ছে। যখনই কাঁটা আগের কোনো ঘরে ফিরে আসে, বোঝো এর মাঝে তুমি পূর্ণ পাক (k-এর গুণিতক) হেঁটেছ। প্রথমবার কোন ঘরে ছিলে তা মনে রাখলে বুঝতে পারো ফিরে আসতে অন্তত দুই ধাপ লেগেছে কি না।

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

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

এটা সরাসরি Subarray Sum Equals K (#13)-এর ভাই। সেখানে আমরা prefix value জমা রাখতাম; এখানে শুধু একটা মোচড় — prefix-এর বদলে prefix % k (remainder) জমা রাখি। ভিত্তি একই prefix-sum + hash map (Pattern 5), নতুন উপাদান modular arithmetic।

ভেতরের যুক্তি¶

মূল সংখ্যাতত্ত্ব: যদি দুটো prefix-এর k দিয়ে ভাগশেষ (remainder) এক হয়, তাহলে তাদের বিয়োগফল k-এর গুণিতক। কারণ prefix[j] ≡ prefix[i] (mod k) মানে prefix[j] - prefix[i] ≡ 0 (mod k), আর সেই বিয়োগফলই হলো (i, j] subarray-র যোগফল। তাই "k-এর গুণিতক যোগফল আছে?" প্রশ্ন বদলে যায় "একই remainder কি আগে দেখেছি?" প্রশ্নে।

কী দিয়ে তথ্য রাখব¶

একটা hash map (remainder → সেই remainder প্রথম যে index-এ দেখা)। count নয়, আমরা প্রথম index রাখি, কারণ দৈর্ঘ্য অন্তত 2 হতে হবে — বর্তমান index থেকে সেই প্রথম দেখা index-এর দূরত্ব মাপতে হবে।

এটি কেন উপযুক্ত¶

আমরা প্রতিটা index-এ জিজ্ঞেস করি "এই remainder কি আগে দেখেছি, আর দূরত্ব ≥ 2?" hash map এই lookup O(1)-এ দেয়। আর প্রথম-দেখা index রাখলে দূরত্ব সবচেয়ে বড় হয়, তাই length ≥ 2 শর্ত মেলার সম্ভাবনাও সর্বোচ্চ থাকে। তাই একই remainder পরে আবার এলে map overwrite করি না।

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: দৈর্ঘ্য ≥ 2 প্রতিটা subarray ধরে যোগফল বের করো, দেখো k-এর গুণিতক কি না।

উদাহরণ

প্রতিটা শুরু i-র জন্য:
    running = nums[i]
    প্রতিটা শেষ j > i-র জন্য:
        running += nums[j]
        running % k == 0 হলে return True
return False

কোথায় বেশি কাজ হচ্ছে¶

দুটো nested loop মানে O(n^2)। আবারও সেই অপচয়: প্রতিটা শুরু-বিন্দুর জন্য বারবার একই অঞ্চলের যোগফল নতুন করে গোনা। অথচ remainder-এর পুনরাবৃত্তি একবার hash map-এ রাখলেই "k-এর গুণিতক যোগফল আছে?" এক pass-এ বলা যায়।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: k-এর গুণিতক যোগফল ⇔ দুই প্রান্তের prefix-এর remainder সমান। তাই আসল subarray যোগফল হিসেব করারও দরকার নেই — শুধু running prefix-এর remainder চিনে রাখলেই হয়, আর "একই remainder আগে দেখেছি কি (≥ 2 দূরে)?" — এটাই উত্তর।

আরও কম কাজে সমাধান¶

seen = {0: -1} দিয়ে শুরু করো (index -1 ধরে নিলে শুরু থেকে শুরু হওয়া subarray-ও দৈর্ঘ্য সঠিক পায়)। running prefix রাখো, প্রতিবার r = prefix % k। r আগে দেখা থাকলে আর দূরত্ব ≥ 2 হলে True; আগে না দেখা থাকলে প্রথমবারের index লিখে রাখো (পরে overwrite নয়)। শেষ পর্যন্ত না মিললে False। O(n)।

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

মোচড়: যখন প্রশ্ন "গুণিতক/divisible", তখন prefix-এর জায়গায় prefix % k জমাও — সমান remainder মানেই গুণিতক ব্যবধান। Subarray Sum Equals K-এর hash map চালটাই, শুধু key হিসেবে value নয়, value-র remainder। ছোট মোচড়, কিন্তু পুরো divisibility-পরিবার এতেই খোলে।

ছবিতে বোঝা¶

nums = [23, 2, 4, 6, 7], k = 6। seen রাখে remainder → প্রথম index; শুরুতে {0: -1}:

উদাহরণ

শুরু: prefix=0, seen={0:-1}
i=0 x=23: prefix=23, r=23%6=5, নতুন → seen={0:-1, 5:0}
i=1 x=2 : prefix=25, r=25%6=1, নতুন → seen={0:-1, 5:0, 1:1}
i=2 x=4 : prefix=29, r=29%6=5, আগে index 0! দূরত্ব 2-0=2 ≥ 2 → True

r=5 আগে index 0-এ দেখা, এখন index 2 — মাঝের [2,4] যোগফল 6, যা 6-এর গুণিতক।

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

Input nums = [23, 2, 6, 4, 7], k = 6:

শুরু: prefix = 0, seen = {0: -1}।
i=0, x=23: prefix=23, r=5, নতুন → seen={0:-1, 5:0}।
i=1, x=2: prefix=25, r=1, নতুন → seen={0:-1, 5:0, 1:1}।
i=2, x=6: prefix=31, r=1, আগে index 1, দূরত্ব 2-1=1 < 2 → না (এবং overwrite নয়)।
i=3, x=4: prefix=35, r=5, আগে index 0, দূরত্ব 3-0=3 ≥ 2 → True।

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

Python¶

Python

def check_subarray_sum(nums, k):
    seen = {0: -1}                     # remainder -> প্রথম যেখানে দেখা
    prefix = 0
    for i, x in enumerate(nums):
        prefix += x
        r = prefix % k                 # mod দিয়ে partner খুঁজি
        if r in seen:
            if i - seen[r] >= 2:       # length >= 2 চাই
                return True
        else:
            seen[r] = i                # শুধু প্রথমবার লিখি
    return False

# ---- tests ----
assert check_subarray_sum([23, 2, 4, 6, 7], 6) == True
assert check_subarray_sum([23, 2, 6, 4, 7], 6) == True
assert check_subarray_sum([23, 2, 6, 4, 7], 13) == False
assert check_subarray_sum([0, 0], 1) == True
assert check_subarray_sum([1, 0], 2) == False
print("সব test pass!")

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

seen = {0: -1} — খালি prefix-এর remainder 0, index -1 ধরে, যাতে শুরু থেকে subarray-ও দৈর্ঘ্য ঠিক পায়।
for i, x in enumerate(nums) — index ও value দুটোই লাগে (দূরত্ব মাপতে index)।
prefix += x — running যোগফল।
r = prefix % k — এই বিন্দুর remainder।
if r in seen: if i - seen[r] >= 2: return True — একই remainder আগে দেখা, আর যথেষ্ট দূরে → গুণিতক subarray পেলাম।
else: seen[r] = i — নতুন remainder হলে শুধু প্রথম index রাখি (দূরত্ব সর্বোচ্চ রাখতে overwrite করি না)।

Output মিলিয়ে দেখা¶

[23,2,4,6,7] k=6-এ remainder 5 আবার আসে index 2-এ (আগে 0), দূরত্ব 2 → True। [23,2,6,4,7] k=6-এ remainder 5 আবার আসে index 3-এ (আগে 0), দূরত্ব 3 → True। একই array k=13-এ কোনো remainder ≥ 2 দূরত্বে পুনরাবৃত্তি হয় না → False। [0,0] k=1-এ remainder 0 index 1-এ (আগে -1), দূরত্ব 2 → True। শেষে print: সব test pass!।

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

সময়¶

O(n) — array-র উপর এক pass, প্রতি element-এ একটা mod আর hash map operation, সবই গড়ে O(1)।

অতিরিক্ত জায়গা¶

O(min(n, k)) — map-এ আলাদা remainder জমে, যা k-টার বেশি হতে পারে না (এবং n-এর বেশিও নয়)।

যে ভুলগুলো এড়াতে হবে¶

count রেখে ফেলা (Subarray Sum Equals K-এর মতো) — এখানে দরকার প্রথম index, যাতে length ≥ 2 যাচাই হয়।
একই remainder এলে index overwrite করা — তাতে দূরত্ব ছোট হয়ে valid উত্তর মিস হতে পারে; শুধু প্রথমবার লেখো।
length ≥ 2 শর্ত ভুলে যাওয়া — তখন একক element-ও (বা শূন্য-দৈর্ঘ্য) ভুলভাবে True দেবে।
seen = {0: -1} initialization বাদ দেওয়া — শুরু থেকে শুরু হওয়া গুণিতক subarray মিস হবে।

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

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: Subarray Sum Equals K (#13)-এর prefix-sum + hash map, যা নিজে Two Sum + math fundamentals-এর prefix idea-র সংকর। নতুন উপাদান modular arithmetic — key হিসেবে prefix % k। সম্পূর্ণ চাল ../patterns.md-র Pattern 5-এ।

পরের অনুশীলন¶

Subarray Sum Equals K — https://leetcode.com/problems/subarray-sum-equals-k/ (এই tracker-এর #13; remainder নয়, raw prefix)
Subarray Sums Divisible by K — https://leetcode.com/problems/subarray-sums-divisible-by-k/ (একই remainder চাল, কিন্তু গোনা)
Contiguous Array — https://leetcode.com/problems/contiguous-array/ (0/1 → -1/+1 করে prefix চাল)

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

Prefix sum + hash map (mod): divisibility-র প্রশ্নে prefix-এর বদলে prefix % k জমাও; সমান remainder মানেই দুই বিন্দুর মধ্যে k-এর গুণিতক যোগফল। প্রথম-দেখা index রাখলে length শর্তও যাচাই করা যায়।

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

ভবিষ্যতের আমাকে: "k-এর গুণিতক যোগফলওয়ালা subarray" শুনলেই prefix % k আর "একই remainder আগে দেখেছি?" মনে পড়বে। দুটো জিনিস ভুলব না — (১) count নয়, প্রথম index রাখা, (২) {0:-1} initialization। এটা #13-এর উপর মাত্র এক লাইন মোচড়, কিন্তু modular চিন্তাটা না বুঝলে ফাঁদে পড়া সহজ।

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