Find total combinations of length 3 such that sum is divisible by a given number and i<j<k

Question

So, I have been trying to find optimum solution for the question, but I can not find a solution which is less than o(n³).

The problem statemnt is :- find total number of triplet in an array such that sum of a[i],a[j],a[k] is divisible by a given number d and i<j<k.

I have tried a multiple solutions but the solutions all reached o(n³). I need a solution that could be less than o(n³)

Answer 1

Let A be an array of numbers of length N:

A = [1,2,3,4,5,6,7,8]

Let D be the divider

D = 4

It is possible to reduce complexity O(N^2) with an extra dictionary that saves you iterating through the array for each pair (a[i],a[j]). The helper dictionary will be built before iterating through the pairs (i,j) with the count of A[k] % D = X. So for any pair A[i], A[j] you can tell how many matching A[k] exist by fetching from a dictionary rather than a loop.

Below is a python implementation that demonstrates the solution

T = 0 # Total possibilities
H = {} # counts all possible (A[k])%D = Key from index k

for k in range(2, len(A)):
  key = A[k]%D
  H[key] = H.get(key,0) + 1

for j in range(1, len(A)):
  if j >= 2:
    H[A[j]%D] -= 1 # when j increments it reduces options for A[k]
  for i in range(j):
    matching_val = (D - (A[i]+A[j]) % D ) % D
    to_add = H.get(matching_val, 0)
    T += to_add

print(T)

Answer 2

1. The key here is to think about the modulus operator. Each number n in the list can be expressed as n = (x*d) + y, where y = n % d.
2. For any 3 integers x, y, z, (x + y + z) will be divisible by d if and only if (x%d + y%d + z%d) % d = 0.
3. You can bucket all numbers in the list based their remainder (ie. n%d)
4. You will have d buckets (ranging from 0 to d-1).
5. Generate all possible triplets using integers in range [0, d-1] that add up to 0, d or 2*d. This will give you the bucket combinations that can be used to obtain a valid triplet.
6. Since you know the number of elements in each bucket, you can calculate the number of valid triplets. (for example, if bucket 0 has 10 elements, the triplet (0,0,0) will have 10*9*8 corresponding triplets).

This algorithm should be enough to set you on track to complete the problem. Leaving out the implementation and other minor details for the reader.