LeetCode Problem 2964

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

LeetCode 2964 - Number of Divisible Triplet Sums

Problem Understanding

The problem gives us an integer array nums and an integer d. We must count how many triplets of indices (i, j, k) satisfy two conditions:

1. The indices are strictly increasing, meaning i < j < k.
2. The sum of the corresponding elements is divisible by d.

In other words, for every possible combination of three distinct positions in the array, we check whether:

$$(nums[i] + nums[j] + nums[k]) \bmod d = 0$$

If the condition is true, that triplet contributes one to the answer.

The input array can contain up to 1000 elements, and each element can be as large as 10^9. The divisor d can also be as large as 10^9.

The array size is the most important constraint. A naive solution would examine every possible triplet, which requires checking:

$$\binom{1000}{3} \approx 166,000,000$$

triplets. This is far too many for an efficient solution.

Since divisibility only depends on remainders modulo d, the actual values are less important than their residues. This observation allows us to avoid enumerating all triplets explicitly.

Some important edge cases include arrays with fewer than three valid combinations, arrays where every triplet is valid, arrays where no triplet is valid, and situations where d is much larger than all numbers in the array. The problem guarantees valid inputs, so we do not need to handle invalid arrays or invalid divisors.

Approaches

Brute Force

The most direct approach is to try every possible triplet (i, j, k).

We use three nested loops:

• The first loop chooses i.
• The second loop chooses j > i.
• The third loop chooses k > j.

For each triplet, we compute the sum and check whether it is divisible by d.

This approach is clearly correct because it examines every possible triplet exactly once and counts those satisfying the condition.

Unfortunately, its time complexity is O(n³). With n = 1000, this results in roughly 166 million triplet checks, which is too slow.

Optimal Approach

Instead of fixing three elements, we can fix the middle index j and count valid pairs (i, k) around it.

Suppose we choose a specific j.

For every k > j, we know:

$$(nums[i] + nums[j] + nums[k]) \bmod d = 0$$

Rearranging:

$$nums[i] \bmod d = (- (nums[j] + nums[k])) \bmod d$$

This means that once j and k are fixed, we only need to know how many previous elements have the required remainder.

We maintain a hash map containing remainder frequencies for all indices before j.

Then for every k > j, we:

1. Compute the required remainder.
2. Look up how many earlier elements have that remainder.
3. Add that count to the answer.

This converts the problem from checking triplets explicitly into counting matching remainders.

Since each pair (j, k) is processed once, the complexity becomes O(n²).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Enumerates every triplet directly
Optimal	O(n²)	O(min(n, d))	Uses remainder frequency counting with a hash map

Algorithm Walkthrough

1. Compute the remainder of each number modulo d. Since divisibility only depends on remainders, we can work entirely with these values.
2. Initialize the answer to zero.
3. Iterate through the array choosing each possible middle index j.
4. Maintain a hash map called remainder_count that stores the frequencies of remainders appearing before j. Initially, before processing a given j, this map contains all indices i < j.
5. For every index k such that k > j, compute:

$$required = (d - (nums[j] + nums[k]) \bmod d) \bmod d$$

This is the remainder needed from some earlier index i. 6. Look up required in the hash map. Every occurrence corresponds to a valid choice of i, so add that frequency to the answer. 7. After finishing all k values for the current j, insert the remainder of nums[j] into the hash map. This ensures it becomes available as a possible i for future middle indices. 8. Continue until all middle indices have been processed. 9. Return the accumulated answer.

Why it works

At every iteration, the hash map contains exactly the remainders of elements whose indices are less than the current middle index j. For each pair (j, k), the algorithm calculates the unique remainder that would make the triplet sum divisible by d. Every occurrence of that remainder in the hash map corresponds to a valid index i < j. Since each valid triplet is counted exactly once when its (j, k) pair is processed, the final answer is correct.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def divisibleTripletCount(self, nums: List[int], d: int) -> int:
        n = len(nums)
        remainders = [num % d for num in nums]

        answer = 0
        remainder_count = defaultdict(int)

        for j in range(n):
            for k in range(j + 1, n):
                required = (d - (remainders[j] + remainders[k]) % d) % d
                answer += remainder_count[required]

            remainder_count[remainders[j]] += 1

        return answer

The implementation begins by converting every number into its remainder modulo d. This simplifies all future divisibility calculations.

The variable remainder_count stores frequencies of remainders seen before the current middle index. At the beginning of each iteration for j, the map contains exactly the values that can serve as valid indices i.

For every k > j, the code computes the remainder needed from an earlier element. Looking up that remainder in the hash map immediately tells us how many valid choices of i exist.

After all pairs involving the current middle index have been processed, the current remainder is inserted into the map so that it can participate as an earlier index in future iterations.

This directly implements the algorithm described above and avoids enumerating all triplets explicitly.

Go Solution

func divisibleTripletCount(nums []int, d int) int {
	n := len(nums)

	remainders := make([]int, n)
	for i := 0; i < n; i++ {
		remainders[i] = nums[i] % d
	}

	answer := 0
	remainderCount := make(map[int]int)

	for j := 0; j < n; j++ {
		for k := j + 1; k < n; k++ {
			required := (d - (remainders[j]+remainders[k])%d) % d
			answer += remainderCount[required]
		}

		remainderCount[remainders[j]]++
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. A map[int]int replaces Python's defaultdict(int), and missing keys automatically return the zero value 0.

The maximum possible answer is:

$$\binom{1000}{3} = 166,167,000$$

which safely fits within Go's int type on all supported LeetCode platforms.

Worked Examples

Example 1

Input

nums = [3,3,4,7,8]
d = 5

Remainders:

[3,3,4,2,3]

j	remainder_count before processing	k	Required Remainder	Matches	Answer
0	{}	1	4	0	0
0	{}	2	3	0	0
0	{}	3	0	0	0
0	{}	4	4	0	0
add 3	{3:1}
1	{3:1}	2	3	1	1
1	{3:1}	3	0	0	1
1	{3:1}	4	4	0	1
add 3	{3:2}
2	{3:2}	3	4	0	1
2	{3:2}	4	3	2	3
add 4	{3:2,4:1}

Final answer:

3

Example 2

Input

nums = [3,3,3,3]
d = 3

Remainders:

[0,0,0,0]

j	Map Before	k	Required	Matches	Answer
0	{}	1	0	0	0
0	{}	2	0	0	0
0	{}	3	0	0	0
add 0	{0:1}
1	{0:1}	2	0	1	1
1	{0:1}	3	0	1	2
add 0	{0:2}
2	{0:2}	3	0	2	4

Final answer:

4

Example 3

Input

nums = [3,3,3,3]
d = 6

Remainders:

[3,3,3,3]

j	Map Before	k	Required	Matches	Answer
0	{}	1	0	0	0
0	{}	2	0	0	0
0	{}	3	0	0	0
add 3	{3:1}
1	{3:1}	2	0	0	0
1	{3:1}	3	0	0	0
add 3	{3:2}
2	{3:2}	3	0	0	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every pair (j, k) is processed exactly once
Space	O(min(n, d))	Hash map stores distinct remainders encountered so far

The outer loop iterates through all possible middle indices, and the inner loop iterates through all later indices. This results in approximately n(n-1)/2 pair evaluations, giving O(n²) time complexity.

The hash map stores frequencies of remainders that have appeared before the current position. There can be at most n distinct remainders observed, so the space complexity is O(min(n, d)).

Test Cases

from typing import List

s = Solution()

assert s.divisibleTripletCount([3, 3, 4, 7, 8], 5) == 3  # example 1
assert s.divisibleTripletCount([3, 3, 3, 3], 3) == 4  # example 2
assert s.divisibleTripletCount([3, 3, 3, 3], 6) == 0  # example 3

assert s.divisibleTripletCount([1], 2) == 0  # fewer than three elements
assert s.divisibleTripletCount([1, 2], 3) == 0  # still no triplet possible

assert s.divisibleTripletCount([1, 2, 3], 3) == 0  # single triplet not divisible
assert s.divisibleTripletCount([1, 2, 3], 6) == 1  # single triplet divisible

assert s.divisibleTripletCount([0, 0, 0, 0], 1) == 4  # all triplets valid

assert s.divisibleTripletCount([5, 10, 15, 20], 5) == 4  # all remainders zero

assert s.divisibleTripletCount([1, 1, 1, 1, 1], 2) == 10  # every triplet sums to 3

assert s.divisibleTripletCount([1000000000, 1000000000, 1000000000], 1000000000) == 1  # large values

assert s.divisibleTripletCount([1, 2, 4, 8, 16], 7) == 2  # mixed remainders

Test Summary

Test	Why
[3,3,4,7,8], d=5	Official example with multiple valid triplets
[3,3,3,3], d=3	Every triplet is valid
[3,3,3,3], d=6	No triplet is valid
[1], d=2	Minimum array size
[1,2], d=3	Fewer than three elements
[1,2,3], d=3	Single triplet that fails
[1,2,3], d=6	Single triplet that succeeds
[0,0,0,0], d=1	Divisor of one
[5,10,15,20], d=5	All remainders are zero
[1,1,1,1,1], d=2	Large number of valid combinations
Large 10^9 values	Verifies handling of maximum element sizes
[1,2,4,8,16], d=7	General mixed remainder scenario

Edge Cases

Arrays With Fewer Than Three Elements

If the array contains fewer than three elements, no valid triplet can exist because the condition requires three distinct indices. The implementation naturally handles this because the nested loops never find a valid (j, k) pair, so the answer remains zero.

All Numbers Have Remainder Zero

When every element is divisible by d, every remainder is zero. In this situation every triplet sum is also divisible by d, and the answer should equal the total number of triplets. The hash map correctly accumulates counts of remainder 0, causing every valid combination to be counted.

Very Large Values and Divisors

Both nums[i] and d can be as large as 10^9. A common mistake is to work directly with full sums repeatedly. The implementation immediately reduces every value modulo d, keeping all remainder calculations within manageable bounds and ensuring efficient processing regardless of input magnitude.

No Valid Remainder Exists

For some (j, k) pairs, the required remainder may not appear among earlier elements. In that case the hash map lookup returns zero and contributes nothing to the answer. This avoids special-case handling and correctly represents the fact that no valid i exists for that pair.