2964. Number of Divisible Triplet Sums - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an integer array nums and an integer d. Your task is to count the number of triplets ((i, j, k)) where $(0 \le i < j < k < \text{nums.length})$ such that the sum of the three numbers is divisible by d; that is:

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

Example Inputs & Outputs:

Example 1:
- Input:
  - nums = [1, 2, 3, 4, 5]
  - d = 3
- Process:
  The valid triplets are:
  - Triplet (1, 2, 3): (1 + 2 + 3 = 6) which is divisible by 3.
  - Triplet (1, 3, 5): (1 + 3 + 5 = 9) which is divisible by 3.
  - Triplet (2, 3, 4): (2 + 3 + 4 = 9) which is divisible by 3.
  - Triplet (3, 4, 5): (3 + 4 + 5 = 12) which is divisible by 3.
- Output: 4
Example 2:
- Input:
  - nums = [0, 0, 0]
  - d = 5
- Process:
  There is only one triplet (0, 0, 0) and (0+0+0=0) which is divisible by 5.
- Output: 1
Example 3:
- Input:
  - nums = [4, 5, 6]
  - d = 3
- Process:
  The only possible triplet is (4, 5, 6) with sum (4+5+6=15), and $(15 \mod 3 = 0)$ .
- Output: 1

Constraints:

$(3 \le \text{nums.length} \le 200)$
$(1 \le \text{nums}[i] \le 100)$
$(1 \le d \le 100)$

Hints

Hint 1:
Since you must check every triplet (i, j, k) where (i < j < k), a natural approach is to use three nested loops. Consider the feasibility given the constraint $(n \le 200)$ .
Hint 2:
Think about using modular arithmetic. Instead of testing the entire sum, you can compute the remainder of each element with respect to d and use those remainders to decide if a triplet’s sum is divisible by d.
Hint 3:
If you can count the frequency of each remainder (i.e. each (r) where $(r = \text{nums}[i] \mod d))$ , you might reduce the number of iterations by counting how many triplets of remainders satisfy $(r_1 + r_2 + r_3 \equiv 0 \pmod d)$ .

Approaches

Approach 1: Brute Force (Triple Nested Loop)

Idea:
Iterate over all possible triplets with three nested loops and check if the sum is divisible by d.
Steps:
1. Loop with index i from 0 to n-3.
2. Loop with index j from i+1 to n-2.
3. Loop with index k from j+1 to n-1.
4. For each triplet ((i, j, k)), check if $((nums[i] + nums[j] + nums[k]) \mod d == 0)$ .
5. Count the valid triplets.
Downside:
Time complexity is $(O(n^3))$ . For (n=200), that is roughly 200³ = 8 million iterations, which is acceptable in many cases but not optimal if the constraints were larger.

Approach 2: Optimized Using Remainder Frequencies

Idea:
Instead of iterating over every triplet, precompute the remainder of each number modulo d and count the frequency of each remainder. Then, for every combination of three remainders ((r_1, r_2, r_3)) such that: $[ (r_1 + r_2 + r_3) \mod d = 0, ]$ count the number of ways to pick elements from the frequency counts (carefully handling cases where the remainders may be the same).
Steps:
1. Create an array freq of size d where freq[r] counts how many numbers have remainder (r) when divided by d.
2. Iterate over all combinations of remainders (r_1, r_2, r_3) (with appropriate ordering to avoid overcounting) and if $((r_1 + r_2 + r_3) \mod d = 0)$ , add the count using combinatorial formulas (using combinations if any remainders are equal).
Trade-off:
This approach runs in $(O(d^3))$ time. Since $(d \le 100)$ , the worst-case is 1,000,000 iterations which is often acceptable. This approach can be more optimal than the triple loop if (n) is large relative to (d), but for $(n \le 200)$ , the brute force is simpler to implement.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Brute Force Approach:
- Time Complexity: $(O(n^3))$ – Three nested loops over the array of size (n). For $(n \le 200)$ , this is about 8 million iterations in the worst case.
- Space Complexity: $(O(1))$ – Only constant extra space is used.
Optimized Remainder Frequency Approach (Alternative):
- Time Complexity: $(O(d^3))$ – Iterating over all remainder combinations, where $(d \le 100)$ .
- Space Complexity: $(O(d))$ for the frequency array.

Step-by-Step Walkthrough and Visual Example

Let’s walk through Example 1:

Input: nums = [1, 2, 3, 4, 5], d = 3

List all Triplets (i, j, k):
- (1, 2, 3): Sum = 6, $(6 \mod 3 = 0)$ → Valid.
- (1, 2, 4): Sum = 7, $(7 \mod 3 \neq 0)$ .
- (1, 2, 5): Sum = 8, not divisible.
- (1, 3, 4): Sum = 8, not divisible.
- (1, 3, 5): Sum = 9, $(9 \mod 3 = 0)$ → Valid.
- (1, 4, 5): Sum = 10, not divisible.
- (2, 3, 4): Sum = 9, valid.
- (2, 3, 5): Sum = 10, not divisible.
- (2, 4, 5): Sum = 11, not divisible.
- (3, 4, 5): Sum = 12, $(12 \mod 3 = 0)$ → Valid.
Count Valid Triplets:
There are 4 valid triplets.

Visual Summary:

Triplets:
1. (1,2,3): 1+2+3 = 6  → 6 mod 3 = 0  (Valid)
2. (1,3,5): 1+3+5 = 9  → 9 mod 3 = 0  (Valid)
3. (2,3,4): 2+3+4 = 9  → 9 mod 3 = 0  (Valid)
4. (3,4,5): 3+4+5 = 12 → 12 mod 3 = 0 (Valid)

Common Mistakes

Off-by-One Errors:
When iterating with nested loops, ensure that the inner loops start at the correct indices ((j = i+1) and (k = j+1)) to avoid counting duplicate triplets.
Modular Arithmetic Mistakes:
Ensure that you correctly check the condition $((\text{sum} \mod d == 0))$ without any extra arithmetic errors.
Overcomplicating:
Given the constraints, a simple triple loop is both easy to implement and sufficient.

Edge Cases

Array Length Exactly 3:
The array itself forms one triplet. For example, nums = [a, b, c].
All Zeros:
Every triplet will have a sum of 0 which is divisible by any d (except when d is 0, but $(d \ge 1)$ per constraints).
No Valid Triplet:
If no combination of three numbers sums to a multiple of d, the result should be 0.

Alternative Variations:
- Counting pairs (instead of triplets) whose sum is divisible by a given number.
- Counting quadruplets with similar divisibility conditions.
Related Problems for Further Practice:
- Divisible Sum Pairs: Count the number of pairs whose sum is divisible by a given integer.
- 3Sum: Find all unique triplets in an array that sum to zero (a classic problem with a similar structure).