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.

Description Hints 4 Solution Video 8:17

2964. Number of Divisible Triplet Sums

Medium67.5% acceptance9 companiesPremium elsewhere, free here

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] <= 10⁹
1 <= d <= 10⁹

Asked at 9 companies

Visa Activision Zscaler AT&T Salesforce

IBM Mathworks Palantir LinkedIn

Topics

Array Hash Table

Hints open one at a time

Hint 1

Fix index L to be the leftmost element of a triplet.

Hint 2

Starting from L, go forward and add the remainder of each element to a map.

Hint 3

Now when you are at index R, consider nums[L] + nums[R] and calculate what the remainder of the third element should be.

Hint 4

Then use the map to find the number of valid third elements between L and R.

8:17

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,3,4,7,8]
5

Input

[3,3,3,3]
3

Input

[3,3,3,3]
6

Your code is saved on this device.Solution