Skip to main content
Talentd

Number of Divisible Triplet Sums - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash Table7 min readAsked at: IBM, Visa, Salesforce +6
Practice this problem

Problem Statement

Given a 0-indexed integer array nums and an integer d, return the number of triplets (i, j, k) such that i < j < k and (nums[i] + nums[j] + nums[k]) % d == 0.

 

Example 1:

Input: nums = [3,3,4,7,8], d = 5
Output: 3
Explanation: The triplets which are divisible by 5 are: (0, 1, 2), (0, 2, 4), (1, 2, 4).
It can be shown that no other triplet is divisible by 5. Hence, the answer is 3.

Example 2:

Input: nums = [3,3,3,3], d = 3
Output: 4
Explanation: Any triplet chosen here has a sum of 9, which is divisible by 3. Hence, the answer is the total number of triplets which is 4.

Example 3:

Input: nums = [3,3,3,3], d = 6
Output: 0
Explanation: Any triplet chosen here has a sum of 9, which is not divisible by 6. Hence, the answer is 0.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 109
  • 1 <= d <= 109

Approach Overview

Problem Overview: Given an integer array nums and an integer d, count the number of triplets (i, j, k) such that i < j < k and (nums[i] + nums[j] + nums[k]) % d == 0. The goal is to avoid checking every possible triplet while still ensuring the divisibility condition is satisfied.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct method enumerates every triplet using three nested loops. For each combination (i, j, k), compute the sum and check if it is divisible by d. This approach requires scanning all n choose 3 combinations, which leads to O(n^3) time complexity. It uses constant extra space since only counters are maintained. While inefficient for large arrays, this version clearly demonstrates the constraint i < j < k and validates the divisibility condition before optimizing.

Approach 2: Hash Table + Enumeration (O(n^2) time, O(d) space)

The optimized solution uses modular arithmetic and a frequency map. Instead of fixing all three indices, fix the middle index j and iterate k to the right. Maintain a hash table that stores the frequency of remainders nums[i] % d for all indices i < j. For each pair (j, k), compute the remainder of their sum and determine the remainder needed from i so the total becomes divisible by d. The required value is needed = (d - (nums[j] + nums[k]) % d) % d. A single hash lookup returns how many valid i indices exist.

This converts the problem from checking explicit triplets to counting compatible remainders. Each pair (j, k) performs constant-time work, producing an overall O(n^2) time complexity. The hash table stores at most d remainder buckets, so space complexity is O(d). The technique relies on properties of modular arithmetic combined with fast lookups from a hash table. Iteration across the array itself is standard array traversal.

Recommended for interviews: The hash table + enumeration approach is what interviewers typically expect. Brute force proves you understand the triplet constraint and divisibility rule, but the optimized method shows you can transform the condition using modular arithmetic and reduce the search space from cubic to quadratic time. Demonstrating the remainder transformation and constant-time hash lookups is the key insight interviewers look for.

Solution

We can use a hash table cnt to record the occurrence times of nums[i] bmod d, then enumerate j and k, calculate the value of nums[i] bmod d that makes the equation (nums[i] + nums[j] + nums[k]) bmod d = 0 hold, which is (d - (nums[j] + nums[k]) bmod d) bmod d, and accumulate its occurrence times to the answer. Then we increase the occurrence times of nums[j] bmod d by one. Continue to enumerate j and k until j reaches the end of the array.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Useful for understanding the constraint i < j < k or when input size is extremely small
Hash Table + EnumerationO(n^2)O(d)General optimal approach using remainder counting and constant-time hash lookups

Video Solution

2964. Number of Divisible Triplet Sums (Leetcode Medium) • Programming Live with Larry • 2,196 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Number of Divisible Triplet Sums easy or hard?
Number of Divisible Triplet Sums is considered a Medium problem. The brute force solution is straightforward, but the optimal approach requires recognizing the modular arithmetic transformation and using a hash table to count compatible remainders efficiently.
Number of Divisible Triplet Sums Python/Java solution
Most implementations follow the same pattern: iterate the array, track remainder frequencies for earlier indices, and count valid matches using modular arithmetic. The algorithm is identical across Python, Java, C++, Go, and TypeScript with O(n^2) time and O(d) space complexity.
How to solve Number of Divisible Triplet Sums in O(n^2)?
Maintain a frequency map of remainders for elements before the current middle index. For every pair (j, k), compute the remainder of nums[j] + nums[k] and determine which remainder from nums[i] would make the total divisible by d. Look up that remainder in the map to count valid triplets. Each lookup takes O(1), resulting in O(n^2) overall time.
What is the best approach for Number of Divisible Triplet Sums?
The most efficient approach uses hash table + enumeration with modular arithmetic. Fix the middle index and iterate the third index while storing frequencies of remainders from earlier elements. Each pair lookup determines how many previous values complete the divisible triplet. This reduces the complexity from O(n^3) to O(n^2) with O(d) extra space.
Is Number of Divisible Triplet Sums asked at Google/Amazon/Meta?
Triplet counting problems and modular arithmetic patterns appear frequently in technical interviews at large tech companies including Google, Amazon, and Meta. Variants often involve counting combinations that satisfy a divisibility or sum constraint while optimizing beyond brute force.
What data structure is used in Number of Divisible Triplet Sums?
A hash table (or hash map) stores frequencies of remainders modulo d. This allows constant-time lookup of how many previous elements can complete a valid triplet. Arrays and modular arithmetic are also key components of the solution.
What is the time complexity of Number of Divisible Triplet Sums?
The optimal solution runs in O(n^2) time. Two indices are enumerated while the third value is counted using a hash table of remainders. Space complexity is O(d) because only remainder frequencies modulo d are stored.

Ready to solve this problem?

Practice Number of Divisible Triplet Sums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays