Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2
3

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:

1
2
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^9
  • 1 <= d <= 10^9

Solution

Method 1 – Hash Map for Pair Sums

Intuition

For each k, count pairs (i, j) with i < j < k such that (nums[i] + nums[j] + nums[k]) % d == 0. For each k, keep a hash map of pair sums modulo d for all previous i, j.

Approach

  1. For each k from 2 to n-1:
    • For each j in 0..k-1, store (nums[i] + nums[j]) % d for i < j in a hash map.
    • For each pair sum mod, if (pair_sum + nums[k]) % d == 0, add its count to answer.
  2. Return total answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    int divisibleTripletSums(vector<int>& nums, int d) {
        int n = nums.size(), ans = 0;
        for (int k = 2; k < n; ++k) {
            unordered_map<int,int> cnt;
            for (int i = 0; i < k; ++i)
                for (int j = i+1; j < k; ++j)
                    cnt[(nums[i]+nums[j])%d]++;
            int need = (d - nums[k]%d)%d;
            ans += cnt[need];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func divisibleTripletSums(nums []int, d int) int {
    n, ans := len(nums), 0
    for k := 2; k < n; k++ {
        cnt := map[int]int{}
        for i := 0; i < k; i++ {
            for j := i+1; j < k; j++ {
                cnt[(nums[i]+nums[j])%d]++
            }
        }
        need := (d - nums[k]%d)%d
        ans += cnt[need]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.*;
class Solution {
    public int divisibleTripletSums(int[] nums, int d) {
        int n = nums.length, ans = 0;
        for (int k = 2; k < n; ++k) {
            Map<Integer,Integer> cnt = new HashMap<>();
            for (int i = 0; i < k; ++i)
                for (int j = i+1; j < k; ++j)
                    cnt.put((nums[i]+nums[j])%d, cnt.getOrDefault((nums[i]+nums[j])%d,0)+1);
            int need = (d - nums[k]%d)%d;
            ans += cnt.getOrDefault(need,0);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun divisibleTripletSums(nums: IntArray, d: Int): Int {
        val n = nums.size
        var ans = 0
        for (k in 2 until n) {
            val cnt = mutableMapOf<Int,Int>()
            for (i in 0 until k)
                for (j in i+1 until k)
                    cnt[(nums[i]+nums[j])%d] = cnt.getOrDefault((nums[i]+nums[j])%d,0)+1
            val need = (d - nums[k]%d)%d
            ans += cnt.getOrDefault(need,0)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def divisibleTripletSums(self, nums: list[int], d: int) -> int:
        n, ans = len(nums), 0
        for k in range(2, n):
            cnt = {}
            for i in range(k):
                for j in range(i+1, k):
                    cnt[(nums[i]+nums[j])%d] = cnt.get((nums[i]+nums[j])%d,0)+1
            need = (d - nums[k]%d)%d
            ans += cnt.get(need,0)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::collections::HashMap;
impl Solution {
    pub fn divisible_triplet_sums(nums: Vec<i32>, d: i32) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for k in 2..n {
            let mut cnt = HashMap::new();
            for i in 0..k {
                for j in i+1..k {
                    *cnt.entry((nums[i]+nums[j])%d).or_insert(0) += 1;
                }
            }
            let need = (d - nums[k]%d)%d;
            ans += *cnt.get(&need).unwrap_or(&0);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    divisibleTripletSums(nums: number[], d: number): number {
        const n = nums.length;
        let ans = 0;
        for (let k = 2; k < n; ++k) {
            const cnt: Record<number, number> = {};
            for (let i = 0; i < k; ++i)
                for (let j = i+1; j < k; ++j)
                    cnt[(nums[i]+nums[j])%d] = (cnt[(nums[i]+nums[j])%d]||0)+1;
            const need = (d - nums[k]%d)%d;
            ans += cnt[need]||0;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^3), where n is the length of nums.
  • 🧺 Space complexity: O(n^2).