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³)

CodePudding user response：

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.

CodePudding user response：

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)