Counting Divisible Collections in the Gallery - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To count the number of non-empty subarrays where the sum of the elements is divisible by k.
  • What input is provided?
    • A list of integers collection_sizes and an integer k.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a prefix sum and a hashmap to count how many times each remainder modulo k has appeared, then use this to determine how many subarrays are divisible by k.

1) Initialize `prefix_sum` to 0 and `count` to 0.
2) Use a dictionary `prefix_count` to store the frequency of each prefix sum modulo `k`.
3) Iterate through `collection_sizes`:
   - Update `prefix_sum` with the current element.
   - Calculate the modulo `k` of the `prefix_sum`.
   - If the modulo has been seen before, add the frequency to `count`.
   - Update `prefix_count` with the current modulo.
4) Return `count`.

⚠️ Common Mistakes

• Not correctly handling negative prefix sums.

I-mplement

def count_divisible_collections(collection_sizes, k):
    prefix_sum = 0
    count = 0
    prefix_count = {0: 1}  # Initialize with 0: 1 to handle cases where the prefix sum itself is divisible by k
    
    for size in collection_sizes:
        prefix_sum += size
        mod = prefix_sum % k
        
        if mod in prefix_count:
            count += prefix_count[mod]
            prefix_count[mod] += 1
        else:
            prefix_count[mod] = 1
    
    return count