7
\$\begingroup\$

I came up with a suitable solution to a HackerRank problem that failed because the execution took longer than 10 seconds on lists that were of very large size.

The problem: Given a list arr and an integer d, find all combinations of length 3 whose sum is divisible by d

My solution:

[
    sum(p) % d
    for p in combinations(arr, r=3)
].count(0)

I simply cannot find a way to optimize this (for time) any more. Can this be further optimized for speed?

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to edit and give it a different title if there is something more appropriate. If you have a link to the hackerrank problem then you could edit the post and paste it in. \$\endgroup\$ Commented Oct 25, 2022 at 23:46
  • \$\begingroup\$ As harold commented on an answer, you need a fundamentally faster algorithm here: one that isn't slower than an "asymptotically optimal" one on the large problem instance every self-respecting competitive programming site is bound to check. \$\endgroup\$
    – greybeard
    Commented Oct 26, 2022 at 5:23
  • \$\begingroup\$ Do an instance of, say, 11 random numbers from 1 to 6 for d=3 by hand. \$\endgroup\$
    – greybeard
    Commented Oct 26, 2022 at 5:25
  • 1
    \$\begingroup\$ Welcome! Would you be able to add the link to the exact problem ? (The wording matters because one may want the list of combinations of the numbers and the solution could be different) \$\endgroup\$
    – SylvainD
    Commented Oct 26, 2022 at 14:57
  • 1
    \$\begingroup\$ Unfortunately, this question was for an interview so I'm not able to provide a direct link \$\endgroup\$ Commented Oct 26, 2022 at 19:50

2 Answers 2

9
\$\begingroup\$

Time complexity of iterating through all the combinations is O(n³).

We can solve it in O(n²) by using the fact that if you know 2 numbers out of 3, you know exactly what modulo-d remainder you need from the 3rd number. If the tests for the problem are properly written, none of the O(n³) solutions will pass, so the only way to get the solution accepted is to go for a better time complexity. So here is how it works.

Put modulo-d remainder of every element in a hashset. Iterate through all possible pairs with a double for loop and for each of them check whether d - (a + b) % d is in the hashset. Such lookups only take O(1) which makes your overall complexity O(n²) (for the double for loop). If the hashset contains the number you're looking for, you have found a combination.

\$\endgroup\$
2
  • \$\begingroup\$ The set needs to be a multiset, of course (i.e. Counter) - and each match contributes the product of the counts of the a, b and c. \$\endgroup\$ Commented Oct 26, 2022 at 7:55
  • \$\begingroup\$ I'm not entirely sure what the implementation of this would look like, would you be able to possibly edit in what it could look like? \$\endgroup\$ Commented Oct 26, 2022 at 19:55
4
\$\begingroup\$

As far as clean code which expresses the intent goes, I quite like your little snippet. In fact, it's the sort of thing which, if I were solving this problem in production code, I'd probably use your suggestion as a reference implementation. It is as near as possible a direct translation of the problem text into Python code. As such its great value is that it's obviously correct, in the sense of the Tony Hoare maxim that you can either go for simplicity with obviously no errors, or complexity with no obvious errors. That makes it valuable, even if it is too slow for production code, for use in tests to validate production code against.

In terms of speeding it up, a few thoughts come to mind immediately.

  1. Minor: Constructing a whole list only to collapse it later may be less efficient than keeping count in a running tally.
  2. Major: combinations(arr, r=3) is a deceptively short way of writing three nested for loops, which means the overall complexity is cubic in the length of arr. That's where you're really losing your time, so you'll have to avoid actually working your way through all the possible combinations one by one. I don't want to ruin the exercise by providing a complete solution, but two (related) ways to get that number down would be to explore dynamic programming to reuse work from previous partial combinations or equivalence classes and combinatorics to count functionally similar elements of arr all at once.
\$\endgroup\$
2
  • 4
    \$\begingroup\$ @RichardNeumann, there are three loops implicit in this combinations call and it is O(n^3), even if each loop does not traverse the entire list and there is a scaling factor. For your intuition, combinations of size 2 loops i from start to end and j from i to end. It counts out a triangle number of tuples rather than a square number of them, but critically is still of quadratic order. \$\endgroup\$
    – Josiah
    Commented Oct 26, 2022 at 0:31
  • 2
    \$\begingroup\$ In the same way, the number of combinations of length 3 is in an array of length 3 is n!/((n-3)!3!), or (n(n-1)(n-2))/6. Again this is cubic in n. \$\endgroup\$
    – Josiah
    Commented Oct 26, 2022 at 0:40

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.