Number of Divisible Triplet Sums

Number of Divisible Triplet Sums - 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.

A triplet is a set of three indices where the sum of the elements at those indices is divisible by d.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,3,4,7,8], d = 5

› Output: 3

💡 Note: Valid triplets are: (0,1,2) with sum 3+3+4=10 (divisible by 5), (0,2,4) with sum 3+4+8=15 (divisible by 5), and (1,2,4) with sum 3+4+8=15 (divisible by 5)

Example 2 — All Same Remainder

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

› Output: 4

💡 Note: Valid triplets: (0,3,6 doesn't exist), (0,1,2) sum=3, (0,3,6 doesn't exist), (1,2,3) sum=6, (2,3,4) sum=9, (3,4,5) sum=12 - all divisible by 3

Example 3 — No Valid Triplets

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

› Output: 0

💡 Note: Only one triplet (0,1,2) with sum 1+2+4=7, and 7%3=1≠0, so no valid triplets

Constraints

3 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 1000
1 ≤ d ≤ 5

Visualization

Tap to expand

Asked in

G Google 25 A Amazon 18 F Facebook 12

The key insight is to group numbers by their remainder when divided by d. The brute force approach checks all triplets in O(n³) time. The optimal solution uses remainder frequencies and combinatorial counting in O(n + d²) time, Space: O(d).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Triple Nested Loop	O(n³)	O(1)	Check all possible triplets and count those with sum divisible by d
Hash Map - Remainder Frequency	O(n + d²)	O(d)	Group numbers by remainder and use combinatorial math to count valid triplets

Brute Force - Triple Nested Loop — Algorithm Steps

Iterate through all i from 0 to n-3
For each i, iterate j from i+1 to n-2
For each j, iterate k from j+1 to n-1
Check if (nums[i] + nums[j] + nums[k]) % d == 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Create all combinations (i,j,k) where i < j < k

Check Divisibility

For each triplet, check if sum % d == 0

Count Valid

Count triplets that satisfy the condition

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int d) {
    int count = 0;
    
    // Check all possible triplets
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                if ((nums[i] + nums[j] + nums[k]) % d == 0) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int d;
    scanf("%d", &d);
    
    printf("%d\n", solution(nums, numsSize, d));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops each running up to n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track indices and count

✓ Linear Space

28.2K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Triple Nested Loop — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler