# Count the number of triplets from an array with sums divisible by 'd'?

I got this question on my test and I did the only logical thing I could think of, which is run 3 nested loops and count each triplet. I obviously wouldn't pass test cases for large arrays...

How can I make this code more efficient?

public static int CountTriplets(int d, List<int> a)
{
int count = 0;
int n = a.Count;

for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int k = j + 1; k < n; k++)
{
if ((a[i] + a[j] + a[k]) % d == 0)
count++;
}
}
}
return count;
}


I don't see a way to avoid the O(n^3) complexity because as far as I can tell, we have to calculate n * (n-1) * (n-2) values. I hope someone can prove me wrong.

However the code can still be optimized.

You access a[i] in the innermost loop, so that is being done (n-1) * (n-2) times.
Same for a[j] and the addition a[i] + a[j] which both happen (n-2) times.

Here is a variant without those redundancies:

public static int CountTriplets2(int d, List<int> a)
{
int count = 0;
int n = a.Count;
for (int i = 0; i < n; i++)
{
var ai = a[i];
for (int j = i + 1; j < n; j++)
{
var aij = ai + a[j];
for (int k = j + 1; k < n; k++)
if ((aij + a[k]) % d == 0)
count++;
}
}
return count;
}


Both methods calculate the modulus value n * (n-1) * (n-2) times, which can also be optimized. To know if (x+y) % d == 0 we can do (x % d) + (y % d) and check if that equals either 0 or d. The values x % d can be calculated just once for every value in the list. Or alternatively, we can subtract d if possible and then check only for 0. This logic can be extended to any number of added values.

This gives us a new variant, which is becoming less readable but I would expect to be faster:

public static int CountTriplets3(int d, List<int> b)
{
int n = b.Count;
var a = new int[n];
for (int i = 0; i < n; i++)
a[i] = b[i] % d;

int count = 0;
for (int i = 0; i < n; i++)
{
var ai = a[i];
for (int j = i + 1; j < n; j++)
{
var aij = ai + a[j];
if (aij >= d)
aij -= d;
for (int k = j + 1; k < n; k++)
{
var aijk = aij + a[k];
if (aijk == 0 || aijk == d)
count++;
}
}
}
return count;
}


We can still optimize this further because we are doing an addition in the innermost loop, but we can actually calculate which a[k] value we would need for a match:

public static int CountTriplets4(int d, List<int> b)
{
int n = b.Count;
var a = new int[n];
for (int i = 0; i < n; i++)
a[i] = b[i] % d;

int count = 0;
for (int i = 0; i < n; i++)
{
var ai = a[i];
for (int j = i + 1; j < n; j++)
{
var aij = ai + a[j];
if (aij >= d)
aij -= d;
var neededForK = aij > 0
? d - aij
: 0;
for (int k = j + 1; k < n; k++)
if (a[k] == neededForK)
count++;
}
}
return count;
}


Test results with 2000 integers on my system, in Release mode, and the same count result:

• CountTriplets -> 3.82 sec
• CountTriplets2 -> 3.30 sec (14% less time)
• CountTriplets3 -> 1.09 sec (72% less time)
• CountTriplets4 -> 0.93 sec (76% less time)
• That looks interesting, unfortunately I lack the ability to understand such formulaic reasoning. A practical implementation (as a separate answer) would be great. I'll happily add it to my timing figures. Sep 22 at 15:14

The question is a cute variation of the 3 sum problem. So lets first go through the classic 2 loop set lookup 3 sum solution.

1. We are given a list to get 3 variables ($$\a\$$, $$\b\$$ and $$\c\$$) and a constant ($$\d\$$). In the original problem $$\d = 0\$$.
2. We know $$\a + b + c = d\$$, so we can rearrange to find $$\c\$$. $$\c = d - a - b\$$
3. We then build a set of the input list. If the language doesn't have a set data type a hash map can be abuse instead. As both have an $$\O(1)\$$ lookup.
4. We then just do input_set.contains(d - a - b) to drop the inner loop.

Here's an example in Python:

# WARNING: the actual code should exclude duplicate indexed values in both the values_set lookup and b
def is_three_sum(values: list[int], d: int = 0) -> bool:
values_set = set(values)
for a in values:
for b in values:
if d - a - b in values_set:
return True
return False


The variation used is cute as we now need to use modular arithmetic. I have renamed the OP's d to e to not conflate with the $$\d\$$ in my answer.

1. We have the equation $$\a + b + c \mod e = d\$$. Where $$\d = 0\$$.
2. We can expand to $$\(a \mod e) + (b \mod e) + (c \mod e) \mod e = d \mod e\$$.
3. Rearrange $$\(c \mod e) = (d \mod e) - (a \mod e) - (b \mod e) \mod e\$$.
4. Simplify $$\c \mod e = d - a - b \mod e\$$.
5. Now all we need to do is precompute values_set to be a set of c % e when we do the lookup.
# WARNING: the actual code should exclude duplicate indexed values in both the values_set lookup and b
def is_three_sum(values: list[int], d: int = 0, e: int = 1) -> bool:
values_set = {v % e for v in values}
for a in values:
for b in values:
if (d - a - b) % e in values_set:
return True
return False


How to fix the WARNING:

• b is simple and is what your code uses.
• values_set can be built at the end of the first loop to not have duplicate values.
def is_three_sum(values: list[int], d: int = 0, e: int = 1) -> bool:
values_set = set()
for i in range(len(values)):
for j in range(i + 1, len(values)):
if (d - values[i] - values[j]) % e in values_set:
return True
return False


NOTE: you can micro-optimise values_set to be an array of size $$\e\$$ for $$\O(1)\$$ lookup which avoids hashing.

Finally lets figure out how to change from an 'is' question (bool) to the count question (int). Let's change return True to count += 1 and see how the code performs with whitebox testing.

• For simplicity $$\e = 1\$$ so all integers sum to 0.

• With values = [0, 1, 2]: (expected output: $$\\binom{3}{3} = 1\$$)

• i = 0, values_set = set(), $$\j \in \{1, 2\}\$$
As values_set is empty none of the inputs can be in the set.

• i = 1, values_set = {0}, $$\j \in \{2\}\$$

• j = 2. The moduloed sum of (0, 1, 2) is 0 which is in values_set. count += 1

The output is 1, as expected.

• With values = [0, 1, 2, 3]: (expected output: $$\\binom{4}{3} = 4\$$)

• i = 0, values_set = set(), $$\j \in \{1, 2, 3\}\$$
As values_set is empty none of the inputs can be in the set.

• i = 1, values_set = {0}, $$\j \in \{2, 3\}\$$

• j = 2. The moduloed sum of (0, 1, 2) is 0 which is in values_set. count += 1
• j = 3. The moduloed sum of (0, 1, 3) is 0 which is in values_set. count += 1
• i = 2, values_set = {0}, $$\j \in \{3\}\$$

• j = 3. The moduloed sum of (0, 2, 3) is 0 which is in values_set. count += 1

The output is 3, which is not as expected.

The problem is we're missing (1, 2, 3). So when i = 2 and j = 3 we should have done count += 2 to account for both (0, 2, 3) and (1, 2, 3).

Lets change values_set to values_count and change values_set.add(values[i] % e) to values_count[values[i] % e] += 1

• With values = [0, 1, 2, 3, 4]: (expected output: $$\\binom{5}{3} = 10\$$)

• i = 0, values_count = [0], $$\j \in \{1, 2, 3, 4\}\$$

• For all values of j we do count += 0.
• i = 1, values_count = [1], $$\j \in \{2, 3, 4\}\$$

• j = 2. The moduloed sum of (0, 1, 2) is 0 which is 1. count += 1
• j = 3. The moduloed sum of (0, 1, 3) is 0 which is 1. count += 1
• j = 4. The moduloed sum of (0, 1, 4) is 0 which is 1. count += 1
• i = 2, values_count = [2], $$\j \in \{3, 4\}\$$

• j = 3. The moduloed sum of (0-1, 2, 3) is 0 which is 2. count += 2
• j = 4. The moduloed sum of (0-1, 2, 4) is 0 which is 2. count += 2
• i = 3, values_count = [3], $$\j \in \{4\}\$$

• j = 4. The moduloed sum of (0-2, 3, 4) is 0 which is 3. count += 3

The output is 10, which is expected.

def count_three_sum(values: list[int], d: int = 0, e: int = 1) -> int:
count = 0
values_count = [0] * e
for i in range(len(values)):
for j in range(i + 1, len(values)):
count += values_count[(d - values[i] - values[j]) % e]
values_count[values[i] % e] += 1
return count


NOTE: all code is untested and provided as a reference

I have graphed the performance of the algorithms. To show how going from an $$\O(n^3)\$$ algorithm to an $$\O(n^2)\$$ algorithm greatly improves the performance of the code.

def test_orig(a: list[int], d: int = 1):
count = 0
n = len(a)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if (a[i] + a[j] + a[k]) % d == 0:
count += 1
return count

def test_peil(values: list[int], e: int = 1, d: int = 0) -> int:
count = 0
values_count = [0] * e
for i in range(len(values)):
for j in range(i + 1, len(values)):
count += values_count[(d - values[i] - values[j]) % e]
values_count[values[i] % e] += 1
return count

def test_peil__micro(values: list[int], e: int = 1, d: int = 0) -> int:
count = 0
values_count = [0] * e
values_count[values[0] % e] += 1
for i in range(1, len(values)):
d_ = d - values[i]
for j in range(i + 1, len(values)):
count += values_count[(d_ - values[j]) % e]
values_count[values[i] % e] += 1
return count

import functools
import random

import matplotlib.pyplot
import numpy
import graphtimer

random.seed(42401)

@functools.cache
def args_conv(size: int) -> tuple[list[int], int]:
arr = list(range(10 * int(size)))
random.shuffle(arr)
return arr[:int(size)], random.randrange(1, max(2, int(size) // 10))

def main():
fig, axs = matplotlib.pyplot.subplots()
axs.set_yscale('log')
axs.set_xscale('log')
(
graphtimer.Plotter(graphtimer.MultiTimer([test_orig, test_peil, test_peil__micro]))
.repeat(10, 10, numpy.logspace(0, 2, num=50), args_conv=args_conv)
.min()
).plot(axs, x_label='len(nums)')
fig.show()
input()

if __name__ == '__main__':
main()

• What did you use 'd' for in your code? You mentioned that d is supposed to be a constant value and you said "where d = 0" but then > d - a - b doesn't make sense to me as remainder set wouldn't contain a negative value Sep 23 at 7:10
• @evirac a+b+c=d shows d is the constant we want to sum to. In your question d=0 -- (a[i] + a[j] + a[k]) % d == 0. "doesn't make sense to me as remainder set wouldn't contain a negative value" are you looking at the first equation or the second which has $d−a−b\mod e$? Do you know -3 % 5 = 2? Sep 23 at 9:38
• oh yeah. that makes sense. Sep 25 at 5:35
• Right idea, but I think you need to keep a counter for values_set, and add that instead of a fixed += 1. Take [2, 8, 14, 20, 26, 32], e=6 as an example. Returns 10, but should return 20. Oct 18 at 0:58
• @DillonDavis I've edited to explain why the values_count algorithm works. Oct 20 at 1:26

While the code completes the task correctly, it has a high time complexity, and for larger input lists, it can be quite inefficient. The time complexity of this code is $$\O(n^3)\$$, where $$\n\$$ is the number of elements in the input list a. This means that as the size of a increases, the execution time of the function will grow significantly.

To make the code run faster, we can use a smarter method . One approach is to use a hashmap (dictionary in C#) to store the frequency of remainders when each element in a is divided by d.

public static int CountTriplets(int d, List<int> a)
{
int count = 0;
int n = a.Count;
Dictionary<int, int> remainderCount = new Dictionary<int, int>();

for (int i = 0; i < n; i++)
{
int remainder = a[i] % d;

if (remainderCount.ContainsKey(remainder))
{
remainderCount[remainder]++;
}
else
{
remainderCount[remainder] = 1;
}
}

for (int i = 0; i < n; i++)
{
int remainder = a[i] % d;
int neededRemainder = (d - remainder) % d;

if (remainderCount.ContainsKey(neededRemainder))
{
count += remainderCount[neededRemainder];
}
if (neededRemainder == remainder)
{
count--;
}
}
return count / 3;
}

• This has a totally different outcome compared to both the original code + the variants in my answer. For 2000 ints (0...1999) and d=3, all those methods return 443778444 but your method gives 444222. Sep 22 at 14:44
• I don't understand what's the logic behind this code.... Sep 22 at 15:17