Given an array a and a number d, I want to count the number of distinct triplets (i,j,k) such that i<j<k and the sum ai + aj + ak is divisible by d.

Example: when a is [3, 3, 4, 7, 8] and d is 5 it should give count as 3:

• triplet with indices (1,2,3) 3+3+4=10
• triplet with indices(1,3,5) 3+4+8=15
• triplet with indices (2,3,4) 3+4+8=15

Constraints:

• 3 ≤ len(a) ≤ 103
• 1 ≤ ai ≤ 109

def count_triplets(arr, d):
 n = len(arr)
 count = 0
 for i in range(n - 2):
 for j in range(i + 1, n - 1):
 for k in range(j + 1, n):
 if (arr[i] + arr[j] + arr[k]) % d == 0:
 count += 1
 return count

I got this for my OA but only came up with O(n3) approach.

Given an array a and a number d, I want to count the number of distinct triplets (i,j,k) such that i<j<k and the sum ai + aj + ak is divisible by d.

Example: when a is [3, 3, 4, 7, 8] and d is 5 it should give count as 3:

• triplet with indices (1,2,3) 3+3+4=10
• triplet with indices(1,3,5) 3+4+8=15
• triplet with indices (2,3,4) 3+4+8=15

Constraints:

• 3 ≤ len(a) ≤ 103
• 1 ≤ ai ≤ 109

def count_triplets(arr, d):
 n = len(arr)
 count = 0
 for i in range(n - 2):
 for j in range(i + 1, n - 1):
 for k in range(j + 1, n):
 if (arr[i] + arr[j] + arr[k]) % d == 0:
 count += 1
 return count

I got this for my OA but only came up with O(n3) approach.

Find distinct triplet (i,j,k) such that i<j<k and sum of the arr[i]+arr[j]+arr[k] is divisible by d?

If arr = [3, 3, 4, 7, 8] and d = 5 it should give count as 3

• triplet with indices (1,2,3) 3+3+4=10
• triplet with indices(1,3,5) 3+4+8=15
• triplet with indices (2,3,4) 3+4+8=15

constraints

• 3<=n<=10^3
• 1<=arr[i]<=10^9

 def count_triplets(arr, d):
 n = len(arr)
 count = 0
 for i in range(n - 2):
 for j in range(i + 1, n - 1):
 for k in range(j + 1, n):
 if (arr[i] + arr[j] + arr[k]) % d == 0:
 count += 1
 return count

I got this for my OA but only came up with O(n^3) approach.

Given an array a and a number d, I want to count the number of distinct triplets (i,j,k) such that i<j<k and the sum ai + aj + ak is divisible by d.

Example: when a is [3, 3, 4, 7, 8] andd is 5 it should give count as 3:

• triplet with indices (1,2,3) 3+3+4=10
• triplet with indices(1,3,5) 3+4+8=15
• triplet with indices (2,3,4) 3+4+8=15

Constraints:

• 3 ≤ len(a) ≤ 103
• 1 ≤ ai ≤ 109

 def count_triplets(arr, d):
 n = len(arr)
 count = 0
 for i in range(n - 2):
 for j in range(i + 1, n - 1):
 for k in range(j + 1, n):
 if (arr[i] + arr[j] + arr[k]) % d == 0:
 count += 1
 return count

I got this for my OA but only came up with O(n3) approach.