3
\$\begingroup\$

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;
}
\$\endgroup\$
0

3 Answers 3

3
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Peter B
    Sep 22, 2023 at 15:14
  • \$\begingroup\$ FWIW I updated my answer. You should hopefully be able to follow the formulaic reasoning. \$\endgroup\$
    – Peilonrayz
    Feb 13 at 16:09
4
\$\begingroup\$

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
        values_set.add(values[i] % e)
    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.

enter image description here

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()
\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – evirac
    Sep 23, 2023 at 7:10
  • \$\begingroup\$ @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? \$\endgroup\$
    – Peilonrayz
    Sep 23, 2023 at 9:38
  • \$\begingroup\$ oh yeah. that makes sense. \$\endgroup\$
    – evirac
    Sep 25, 2023 at 5:35
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 18, 2023 at 0:58
  • \$\begingroup\$ @DillonDavis I've edited to explain why the values_count algorithm works. \$\endgroup\$
    – Peilonrayz
    Oct 20, 2023 at 1:26
-1
\$\begingroup\$

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;
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Peter B
    Sep 22, 2023 at 14:44
  • 1
    \$\begingroup\$ I don't understand what's the logic behind this code.... \$\endgroup\$
    – evirac
    Sep 22, 2023 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.