Understanding Count Triplets HackerRank

Question

I have been working on this challenge: Count Triplets, and after a lot of hard work, my algorithm did not work out for every test case.

Since in the discussion, I have seen a code and tried to find out the real functionality of the code, I am still not able to understand how, this code works.

Solution:

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)
v3 = defaultdict(int)
count = 0
for k in arr:
    count += v3[k]
    v3[k*r] += v2[k]
    v2[k*r] += 1
print(count)

The above code works for every test case perfectly. I have tested for value of k, v2, v3 to understand but still don't understand how the code works so smooth with the counting triplets. I cannot think of that solution in my dreams too. I wonder how people are so smart to work out this solution. Nevertheless, I would be glad if I would get the proper explanation. Thanks

Output for k,v2,v3

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)
v3 = defaultdict(int)
count = 0
for k in arr:
    count += v3[k]
    v3[k*r] += v2[k]
    v2[k*r] += 1
    print(k, count, v2, v3)

OUTPUT

1 0 defaultdict(<class 'int'>, {1: 0, 3: 1}) defaultdict(<class 'int'>, {1: 0, 3: 0})                                                  
3 0 defaultdict(<class 'int'>, {1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {1: 0, 3: 0, 9: 1})                                      
9 1 defaultdict(<class 'int'>, {27: 1, 1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {27: 1, 1: 0, 3: 0, 9: 1})                        
9 2 defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 0, 9: 1})                        
27 4 defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 1, 81: 1, 9: 1}) defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 0, 81: 2, 9: 1})         
81 6 defaultdict(<class 'int'>, {1: 0, 3: 1, 243: 1, 81: 1, 9: 1, 27: 2}) defaultdict(<class 'int'>, {1: 0, 3: 0, 243: 1, 81: 2, 9: 1, 
27: 2})

Answer 1

1. The problem

The function has two parameters, namely:

• arr: an array of integers
• r: an integer, the common ratio

So, the input can be something like

arr: [1, 2, 2, 4]
r: 2

The goal is to return the count of triplets that form a geometric progression.

---

2. How to solve it

To solve it there's variou ways. For instances, from SagunB based on the comment from RobertsN

• Can be done in O(n) -> single pass through data
• No division necessary and single multiplications by R are all that's needed
• Using map(C++) or dict(Java, Python) is a must -> can be unordered map (saves O(logN))
• Try to think forward when reading a value -> will this value form part of a triplet later?
• No need to consider (R == 1) as a corner case

from collections import Counter

# Complete the countTriplets function below.
def countTriplets(arr, r):
    r2 = Counter()
    r3 = Counter()
    count = 0
    
    for v in arr:
        if v in r3:
            count += r3[v]
        
        if v in r2:
            r3[v*r] += r2[v]
        
        r2[v*r] += 1

    return count

Or like you said

from collections import defaultdict

# Complete the countTriplets function below.
def countTriplets(arr, r):
    v2 = defaultdict(int)
    v3 = defaultdict(int)
    count = 0
    for k in arr:
        count += v3[k]
        v3[k*r] += v2[k]
        v2[k*r] += 1
    return count

---

3. End result

Both cases will pass all the current 13 Test cases in HackerRank

---

4. Explanation of your case

Comments from RobertsN pretty much explain your code (which is very similar to yours). Still, for a better clarification to understand how the code works, just print the what happens to count, v2 and v3.

Assuming you'll have as input

4 2
1 2 2 4

The expected output is

2

Also, we know that by definition both v2 and v3 will look like

defaultdict(<class 'int'>, {})

which leaves the for loop left to understand. What can cause some confusion there is the operator += but that was already addressed by me in another answer.

So, now to understand the rest we can change the loop to

for k in arr:
    print(f"Looping...")
    print(f"k: {k}")
    print(f"v3_before_count: {v3}")
    count += v3[k]
    print(f"count: {count}")
    print(f"k*r: {k*r}")
    print(f"v3_before: {v3}")
    v3[k*r] += v2[k]
    print(f"v3[k*r]: {v3[k*r]}")
    print(f"v2[k]: {v2[k]}")
    print(f"v3_after: {v3}")
    print(f"v2_before: {v2}")
    v2[k*r] += 1
    print(f"v2_after: {v2}")
    print(f"v2[k*r]: {v2[k*r]}")

Will allow you to see

Looping...
k: 1
v3_before_count: defaultdict(<class 'int'>, {})
count: 0
k*r: 2
v3_before: defaultdict(<class 'int'>, {1: 0})
v2_before_v3: defaultdict(<class 'int'>, {1: 0})
v3[k*r]: 0
v2[k]: 0
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0})
v2_before: defaultdict(<class 'int'>, {1: 0})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1})
v2[k*r]: 1
Looping...
k: 2
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0})
count: 0
k*r: 4
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0})
v3[k*r]: 1
v2[k]: 1
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 1})
v2[k*r]: 1
Looping...
k: 2
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
count: 0
k*r: 4
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v3[k*r]: 2
v2[k]: 1
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 1})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2})
v2[k*r]: 2
Looping...
k: 4
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
count: 2
k*r: 8
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v3[k*r]: 2
v2[k]: 2
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2, 8: 2})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2, 8: 1})
v2[k*r]: 1

and extract the desired illations. What can we observe from that?

• count increases in the last loop from 0 to 2.
• k goes through all values of the arr - so it'll be 1, 2, 2 and 4.
• in the initial loop, v3_before_count is {} and v3_before is {1:0}
• etc.

Most likely this process will lead to questions and answering them will leave you closer to understand it.

Answer 2

So the code is tracking potential pairs and triplets as it walks through the array.

For each value in the array:
    // Increment count by the number of triplets that end with k
    count += v3[k]
    // Increment the number of potential triplets that will end with k*r
    v3[k*r] += v2[k]
    // Increment the number of potential pairs that end with k*r
    v2[k*r] += 1  

The number of triplets for any given k is the number of pairs for any given k/r that we've encountered up to this point. Note throughout the loop, v3[k] and v2[k] will often be zero, until they hit our predicted k*r value from a previous iteration.

Answer 3

I have been trying to make sense of it and finally, this C# code should be clear to follow

static long countTriplets(List<long> arr, long r)
{
    //number of times we encounter key*r
    var doubles = new Dictionary<long, long>();
    //number of times we encounter a triplet
    var triplets = new Dictionary<long, long>();
    long count = 0;
    foreach (var key in arr)
    {
        long keyXr = key * r;

        if (triplets.ContainsKey(key))
            count += triplets[key];

        if (doubles.ContainsKey(key))
        {
            if (triplets.ContainsKey(keyXr))
                triplets[keyXr] += doubles[key];
            else
                triplets.Add(keyXr, doubles[key]);
        }

        if (doubles.ContainsKey(keyXr))
            doubles[keyXr]++;
        else
            doubles.Add(keyXr, 1);
    }
    return count;
}

Answer 4

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)   #if miss get 0
v3 = defaultdict(int)   #if miss get 0 
count = 0`enter code here`
for k in arr:
    #updating the count, starts propagating with delay=2 elements
    count += v3[k]

    # number of triplets with last component ending
    # on index i of k in array
    v3[k*r] += v2[k]

    # number of pairs with last component ending
    # on index i of k in array
    v2[k*r] += 1
print(count)

Best to understand it on example - suppose we have array 11111, and we are on i=3, so 111>1<1.

v2 has currently count for 111, 11>1< there are two pairs ending with >1< generally n-1 for length(array)=n.

Now at v3 we construct count recursively from v2, as follows: for each pair created and counted with v2 we assign last component there are n such options for #pairs = n.

So for i=3:

11.1 (v2=1) //this pair remains by sum
+
.111 (v2=2) //these are new
1.11 (v2=2)

Hope this helps!

Answer 5

Potential value of number X : the number of triplets there are if any number uses X as the precedence to completely form a triplet.

Let take an example: 1 2 4 with r = 2.

S1: with 1: no triplet cause 1/2=0.5 and 1/2/2=0.25 not available. Add 1 to hashmap.

S2: with 2: 1 potential triplet can be formed if the final number is reached (the 4). Add 2 to hashmap.

S3: with 4: 1 potential triplet can be form if the final number is reached (the 8). Add 4 to hashmap. At the same time we have 1 triplet because 4/2 & 4/2/2 exist in the hashmap.

But how do we know there only 1? Because in order to reach to number 4 of a triplet, you must go through number 2, and we only has 1 number 2 before number 4.

So total is 1. Easy.

What if the input is 1 2 2 2 4?

we have the potential: 1: 0; 2: 1 number 1; 4: 3 number 2 => 3 triplets

Let add 1 to the input, we have: 1 1 2 2 2 4 with r=2

With the 1st 2, we have 2 potential triplet because there are 2 number 1 before it.

With the 2nd 2, we have double

With the 3rd 2, we have triple

So the total is 2(number 1) x 3 (number 2) = 6 potential triplet

And when the index reached the number 4, similar to Step 3 above, we have total triplet is 6.

This is demonstration of 2 hashmap we iterated through the array:

Input	Potential	Count
1 1 2 2 2 4	{1:0, 2:6, 4:3}	{1:2, 2:3, 4:1}
1 1 2 2 2 4 8 16	{1:0, 2:6, 4:3, 8:1, 16:1}	{1:2, 2:3, 4:1, 8:1, 16:1 }

As the second input in table above, we can say:

with triplet number (1,2,4) we have 6 triplets (potential at number 2)

with triplet number (2,4,8) we have 3 triplets (potential at number 4)

with triplet number (4,8,16) we have 1 triplets (potential at number 8)

SO total is 10 triplets.

And this is my javascript solution

function countTriplets(arr, r) {
const numberAtThisPointOf = {};
const potentialTripletOf = {};
let total = 0;

for (let i = 0; i < arr.length; i++) {
  const key = arr[i];
  if (numberAtThisPointOf[key] === undefined) {
    potentialTripletOf[key] = 0;
    numberAtThisPointOf[key] = 0;
  }
  
  // if key is final part of a triplet, mean the other 2 smaller numbers exist, the `key % r === 0` & `(key/r) % r === 0` to avoid decimal number in javascript
  if (key % r === 0 && numberAtThisPointOf[key/r] !== undefined & numberAtThisPointOf[key/r/r] !== undefined && (key/r) % r === 0) {
    total += potentialTripletOf[key/r];
  }
  
  // update potential case of current key
  if (numberAtThisPointOf[key/r] !== undefined && key % r === 0) {
    potentialTripletOf[key] += numberAtThisPointOf[key/r];
  }
  
  numberAtThisPointOf[key]++;
  
  }
  return total; 
}

Answer 6

Can be thoughts like below.

Geometric progression is form of : A, AR , ARR,....

Now consider if element in arr is :

1. element == ARR or third term of triplet means we have completed the triplet hence update the count.

2. element == AR or second term of triplet so the next element in GP will be(element multiplied by R ) ARR and to be updated in ARR or r3 dictionary .

3. element == A or first term so next element in GP will be (element multiplied R) AR hence to be updated in AR or r2 dictionary.