Longest Subarray with Sum Divisible by K

📋

Problem

Imagine you are analyzing a sequence of daily sales and want to find the longest stretch where the total sales are divisible by a fixed number K, helping you identify periodic trends.

Given an integer array nums and an integer k, find the length of the longest subarray whose sum is divisible by k. Return the length of such subarray. If no such subarray exists, return 0.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^92 ≤ k ≤ 10^9

Edge cases: All elements are zero → entire array lengthNo subarray sum divisible by k → output 0Negative numbers in array → must handle modulo correctly

</>

IDE

def longest_subarray_div_by_k(nums: list[int], k: int) -> int:public int longestSubarrayDivByK(int[] nums, int k)int longestSubarrayDivByK(vector<int>& nums, int k)function longestSubarrayDivByK(nums, k)

def longest_subarray_div_by_k(nums, k):
    # Write your solution here
    pass

class Solution {
    public int longestSubarrayDivByK(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int longestSubarrayDivByK(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function longestSubarrayDivByK(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not initializing remainder 0 at index -1, missing subarrays starting at index 0.✅ Initialize hashmap with remainder 0 mapped to index -1 before iterating.

Wrong: Incorrect length less than actualNot updating max length when remainder repeats; only checking current sums.✅ Update max length when current remainder seen before: max_length = max(max_length, current_index - first_index).

Wrong: Wrong result with negative numbersModulo operation returns negative remainder for negative sums.✅ Normalize remainder with (remainder + k) % k to ensure non-negative keys.

Wrong: TLE or timeoutUsing brute force O(n^2) approach instead of O(n) prefix sum + hash map.✅ Implement prefix sums and store first occurrence of each remainder in a hash map for O(n) solution.

Wrong: Incorrect result when k=1Not handling k=1 special case where all sums are divisible.✅ Return array length immediately if k == 1.

✓

Test Cases

Focus on handling boundary cases like empty arrays and single elements correctly.

Watch out for negative numbers and special values of k like 1.

Optimize your solution to O(n) time using prefix sums and a hash map to avoid TLE.

t1_01basic

Input{"nums":[2,7,6,1,4,5],"k":3}

Expected4

⏱ Performance - must finish in 2000ms

The subarray [7, 6, 1, 4] sums to 18, divisible by 3, length 4 is longest.

💡 Consider prefix sums and their remainders modulo k.

💡 Use a hash map to store first occurrence of each remainder.

💡 Update max length when a remainder repeats, length = current_index - first_index.

Why it failed: Incorrect output means prefix sum modulo logic or hash map usage is wrong; fix by storing first occurrence of each remainder and updating max length accordingly.

✓ Correctly finds longest subarray with sum divisible by k using prefix sums and hash map.

t1_02basic

Input{"nums":[5,0,5,0,5],"k":5}

Expected5

⏱ Performance - must finish in 2000ms

Entire array sums to 15, divisible by 5, length 5 is longest.

💡 Check if entire array sum modulo k is zero.

💡 Prefix sums modulo k can be zero at start and end.

💡 If remainder zero appears at index j, subarray from start to j is valid.

Why it failed: Failing this means code misses subarrays starting at index 0 with remainder zero; fix by initializing remainder 0 at index -1 in hash map.

✓ Correctly handles subarrays starting at index 0 with sum divisible by k.

t2_01edge

Input{"nums":[],"k":3}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so result is 0.

💡 Consider what happens when input array is empty.

💡 No subarrays exist, so max length must be zero.

💡 Return 0 immediately if array length is zero.

Why it failed: Code crashes or returns non-zero for empty input; fix by handling empty array case explicitly.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[7],"k":5}

Expected0

⏱ Performance - must finish in 2000ms

Single element 7 is not divisible by 5, so no valid subarray.

💡 Check single element arrays carefully.

💡 If element modulo k is not zero, result is zero.

💡 Return 1 only if element % k == 0.

Why it failed: Returns 1 incorrectly for single element not divisible by k; fix by checking element modulo k before returning length.

✓ Correctly returns 0 when single element not divisible by k.

t2_03edge

Input{"nums":[0,0,0,0],"k":7}

Expected4

⏱ Performance - must finish in 2000ms

All zeros sum to 0, divisible by any k, so entire array length 4 is answer.

💡 All zeros sum to zero, which is divisible by any k.

💡 Check if code handles zero sums correctly.

💡 Ensure prefix sum modulo zero remainder is handled properly.

Why it failed: Fails to recognize zero sum subarray; fix by initializing remainder 0 at index -1 and updating max length accordingly.

✓ Correctly returns full length for all zero array.

t3_01corner

Input{"nums":[1,2,3,4,5],"k":5}

Expected5

⏱ Performance - must finish in 2000ms

Sum of entire array is 15, divisible by 5, so length 5 is longest.

💡 Check if code correctly handles subarrays that span entire array.

💡 Verify prefix sums and remainder calculations for full length.

💡 Ensure remainder 0 at last index updates max length to n.

Why it failed: Fails to update max length when remainder 0 appears at last index; fix by initializing remainder 0 at index -1 and updating max length accordingly.

✓ Correctly identifies full array as valid subarray.

t3_02corner

Input{"nums":[4,-1,2,1],"k":5}

Expected3

⏱ Performance - must finish in 2000ms

Subarray [4, -1, 2] sums to 5, divisible by 5, length 3 is longest.

💡 Negative numbers affect modulo; handle negative modulo correctly.

💡 Use (prefix_sum % k + k) % k to get positive remainder.

💡 Store first occurrence of each remainder properly.

Why it failed: Incorrect handling of negative modulo leads to wrong remainder keys; fix by normalizing remainder with (mod + k) % k.

✓ Correctly handles negative numbers and modulo.

t3_03corner

Input{"nums":[1,2,3,4,5],"k":1}

Expected5

⏱ Performance - must finish in 2000ms

Any sum modulo 1 is zero, so entire array length 5 is answer.

💡 Modulo 1 always yields zero remainder.

💡 Check if code handles k=1 edge case efficiently.

💡 Return array length immediately if k=1.

Why it failed: Fails to handle k=1 special case, causing incorrect or slow results; fix by returning array length immediately when k=1.

✓ Correctly returns full length for k=1.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],"k":97}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) prefix sum + hash map solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out for n=100.

💡 Use prefix sums and hash map to achieve O(n) time.

💡 Store first occurrence of each remainder to find max length efficiently.

Why it failed: TLE indicates brute force or inefficient approach; fix by implementing O(n) prefix sum + hash map solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Given the following code, what is the return value when the input string is "aabc"?

easy

A. 2

B. 1

C. -1

D. 0

Solution

1. Step 1: Trace frequency and first_index dictionaries

   For "aabc": freq={'a':2, 'b':1, 'c':1}, first_index={'a':0, 'b':2, 'c':3}

2. Step 2: Find minimum index with frequency 1

   Characters with count 1 are 'b' at index 2 and 'c' at index 3; minimum is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First unique char is 'b' at index 2 [OK]

Hint: Check frequency and first occurrence carefully [OK]

Common Mistakes:

• Returning character instead of index
• Off-by-one index errors
• Ignoring multiple unique chars

2. You are given two integer arrays and need to find all elements that appear in both arrays, including duplicates, with the output containing each common element as many times as it appears in both arrays. Which approach guarantees the most efficient solution in terms of time complexity for large inputs?

easy

A. Sort both arrays and use two pointers to traverse them simultaneously, collecting common elements.

B. Use dynamic programming to build a table of common elements counts.

C. Use nested loops to check each element of the first array against all elements of the second array.

D. Use a greedy approach to pick elements from the first array that appear earliest in the second array.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding all common elements including duplicates, so a method that preserves counts is needed.

2. Step 2: Evaluate approaches

   Sorting both arrays and using two pointers allows linear traversal after sorting, efficiently finding all duplicates. Nested loops are O(m*n), DP is not applicable here, and greedy does not guarantee correct counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is O(m log m + n log n) and handles duplicates correctly [OK]

Hint: Sorting + two pointers handles duplicates efficiently [OK]

Common Mistakes:

• Thinking nested loops are efficient enough
• Confusing DP applicability
• Assuming greedy works for duplicates

3. What is the time complexity of the optimal character frequency counting approach for grouping anagrams, given n strings each of length k?

medium

A. O(n * k log k)

B. O(n^2 * k log k)

C. O(n * k)

D. O(n * k^2)

Solution

1. Step 1: Identify loops in the algorithm

   Outer loop runs n times, inner loop counts characters in each string of length k.

2. Step 2: Analyze operations inside loops

   Counting frequency is O(k), creating tuple key is O(26) constant, appending to map is O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(n * k) [OK]

Hint: Frequency counting is linear in string length [OK]

Common Mistakes:

• Confusing sorting cost with counting
• Assuming k log k due to sorting
• Mistaking quadratic complexity

4. Identify the bug in the following Two Sum implementation using a hash map:

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(nums):
        if num in seen:
            return [seen[num], i]
        complement = target - num
        seen[complement] = i

What is the issue?

medium

A. Line 5: Checking if num in seen instead of complement

B. Line 7: Storing complement as key instead of num

C. Line 6: Returning indices in wrong order

D. Line 4: Using a dictionary instead of a list

Solution

1. Step 1: Understand what is stored in the hash map

   The code stores complement as key with current index as value, which is incorrect because we need to store the number itself to check for complements later.

2. Step 2: Identify the bug line

   Line 7 stores complement as key instead of num, causing lookups to fail or return incorrect results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Hash map keys must be numbers seen, not complements [OK]

Hint: Store numbers as keys, not complements, in hash map [OK]

Common Mistakes:

• Storing complements as keys
• Returning indices in wrong order
• Using list instead of dict for lookups

5. Suppose the array nums can contain negative numbers and you want to count subarrays summing to k. Which modification to the prefix sum + hash map approach correctly handles this scenario?

hard

A. Keep the prefix sum + hash map approach unchanged, as it already handles negative numbers correctly.

B. Sort the array first, then use two pointers to find subarrays summing to k.

C. Use a sliding window approach since negative numbers allow shrinking the window arbitrarily.

D. Use nested loops to check all subarrays because prefix sums fail with negative numbers.

Solution

1. Step 1: Understand sliding window limitations

   Sliding window fails with negative numbers because sums can decrease unpredictably.

2. Step 2: Verify prefix sum + hash map suitability

   Prefix sums with hash map count frequencies and handle negative numbers naturally without sorting.

3. Step 3: Evaluate other options

   Sorting breaks subarray continuity; nested loops are correct but inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Prefix sum + hash map is the robust solution for negatives [OK]

Hint: Prefix sums + hash map handles negatives; sliding window does not [OK]

Common Mistakes:

• Trying sliding window with negatives
• Sorting array breaks subarray continuity
• Assuming prefix sums fail with negatives