1 of 8

Can someone give a optimized 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

I got this for an online test I could only come up with the O(n^3) approach. Just tell me an approach I even tried the 3sum approach but failed.

    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```