LeetCode Solutions Blog

Number of Divisible Triplet Sums

Number: 3254

Difficulty: Medium

Paid? Yes

Problem Description

Given a 0-indexed integer array nums and an integer d, count the number of triplets (i, j, k) with i < j < k such that the sum of the corresponding elements is divisible by d.

Key Insights

Pre-compute each number’s remainder modulo d to simplify the sum computations.
Use a double loop to fix the first two indices (i, j) and then determine the necessary remainder for the third index k.
Build a suffix frequency structure for remainders so that for each index j, you can quickly obtain the count of valid k-values (k > j) having the required remainder.
Although a naive brute force triple loop would be O(n^3), using the suffix count reduces it to O(n^2), which is acceptable for n up to 1000.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n) (for storing suffix remainder counts; note that the number of distinct remainders encountered is at most n)

Solution

The solution starts by computing the modulo d value for each element in nums. It then precomputes a suffix frequency array such that for every index, you have a dictionary counting the occurrence of each remainder from that index to the end. For every pair (i, j) with i < j, we calculate the required remainder for k so that (nums[i] + nums[j] + nums[k]) % d == 0 can hold. Using the suffix frequency array, we quickly find how many valid indices k exist for each chosen pair. This efficient counting avoids the need for a third nested loop and leverages hash tables to compute the required frequency counts in O(1) time per lookup.

Code Solutions

# Python Code Solution

def divisibleTripletSums(nums, d):
    n = len(nums)
    # Precompute remainders for each number
    remainders = [num % d for num in nums]
    
    # Build suffix frequency array: suffix_freq[i] holds frequency of remainders from index i to end.
    suffix_freq = [None] * (n + 1)
    suffix_freq[n] = {}  # empty dictionary for index n (no elements)
    for i in range(n - 1, -1, -1):
        # Copy the frequency map from the next index.
        current = suffix_freq[i + 1].copy()
        rem = remainders[i]
        current[rem] = current.get(rem, 0) + 1
        suffix_freq[i] = current
    
    count = 0
    # Iterate over all pairs (i, j) and use the suffix frequency for indices > j.
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            # Compute sum of remainders for indices i and j
            current_sum = (remainders[i] + remainders[j]) % d
            # We need a third remainder that when added gives 0 modulo d
            required = (-current_sum) % d
            # Increment the count by the number of indices k > j with remainder required.
            count += suffix_freq[j + 1].get(required, 0)
    
    return count

# Example usage:
print(divisibleTripletSums([3, 3, 4, 7, 8], 5))  # Expected output: 3
print(divisibleTripletSums([3, 3, 3, 3], 3))     # Expected output: 4
print(divisibleTripletSums([3, 3, 3, 3], 6))     # Expected output: 0