Weekly Challenge 199
Task 1: Good Pairs
You are given a list of integers,
Write a script to find the total count of Good Pairs. A pair
(i, j) is called good if
list[i] == list[j] and
i < j.
One of the challenges when completing these tasks is needless optimizations. Given that the input list is relatively small there is a fine line between being clever and just brute forcing the solution.
The brute force solution is (where
n is the length of the array) to go through all combinations of i and j (where
i is an iterator from
n - 2 and
j is an iterator from
i + 1 to
n - 1), and count the occurrences where the value in that position is the same. And that's a perfectly acceptable solution in solving the task. I'd approve that pull request every day of the week :)
The solution I took is a little more complex, but will work on extremely large lists better. The first thing I do is count the frequency of each 'integer'. I put that in quotes as in Python they really are strings. This is stored as the
freq dict (hash in Perl).
I then loop through the frequency counts (the values of the
freq dict). If the frequency is greater than one, we have good pairs. The number pairs is the sum of
1 + ... + n-1. Rather than calculating the sum by hand, we know that the sum of
n can be expressed a
n × (n + 1) ÷ 2, which is the formula that I use.
$ ./ch-1.py 1 2 3 1 1 3 4 $ ./ch-1.py 1 2 3 0 $ ./ch-1.py 1 1 1 1 6
Task 2: Good Triplets
You are given an array of integers,
@array and three integers
Write a script to find out total Good Triplets in the given array.
A triplet array[i], array[j], array[k] is good if it satisfies the following conditions:
1) 0 <= i < j < k <= n (size of given array)
1) abs(array[i] - array[j]) <= x
1) abs(array[j] - array[k]) <= y
1) abs(array[i] - array[k]) <= z
My first observation is that
k can be the size of the array. This will cause an out of bounds errors. For example, if an array has three elements,
array is not valid. So I'm assuming that for the first condition it is meant that
k < n.
My next observation is that this very similar to the first task in week 196, so most of the code comes from that solution.
The first thing I do is remove the last three values from the input to represent
For this task I used the combinations method from itertools (Python) or Algorithm::Combinatorics (Perl) to generate all combinations of positions (not values) from
0 to one less than the length of the array.
For each iteration, I (numerically) sort the numbers to ensure
i < j < k. I then check if the other three criteria are met. If it is, I add one to
$ ./ch-2.py 3 0 1 1 9 7 7 2 3 4 $ ./ch-2.py 1 1 2 2 3 0 0 1 0
Top comments (0)