## Hackerrank - Count Triplets Solution

You are given an array and you need to find number of triplets of indices such that the elements at those indices are in geometric progression for a given common ratio and .

For example, . If , we have and at indices and .

**Function Description**

Complete the *countTriplets* function in the editor below. It should return the number of triplets forming a geometric progression for a given as an integer.

countTriplets has the following parameter(s):

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

**Input Format**

The first line contains two space-separated integers and , the size of and the common ratio.

The next line contains space-seperated integers .

**Constraints**

**Output Format**

Return the count of triplets that form a geometric progression.

**Sample Input 0**

```
4 2
1 2 2 4
```

**Sample Output 0**

`2`

**Explanation 0**

There are triplets in satisfying our criteria, whose indices are and

**Sample Input 1**

```
6 3
1 3 9 9 27 81
```

**Sample Output 1**

`6`

**Explanation 1**

The triplets satisfying are index , , , , and .

**Sample Input 2**

```
5 5
1 5 5 25 125
```

**Sample Output 2**

`4`

**Explanation 2**

The triplets satisfying are index , , , .

### Solution in C++

### Solution in Python

```
from collections import Counter
def countTriplets(arr, r):
a = Counter(arr)
b = Counter()
s = 0
for i in arr:
j = i//r
k = i*r
a[i]-=1
if b[j] and a[k] and not i%r:
s+=b[j]*a[k]
b[i]+=1
return s
n,r = map(int,input().split())
arr = list(map(int,input().split()))
print(countTriplets(arr, r))
```

*Solution*

Let arr = [1, 3, 9, 9, 27, 81]

First we count the number of occurrence and assign it to a.

Then create another variable b which is an empty counter.

```
>>> a = Counter(arr)
>>> a
Counter({1: 1, 3: 1, 9: 2, 27: 1, 81: 1})
>>> b = Counter()
>>> b
Counter()
```

Our algorithm works by assuming current number is center of triplet.

For example given r = 10, and current number is 10 we will assume the current number as the center of triplet.

And thus our triplet will be (1,10,100). Now when we see 10 we just have to find whether we have both 1 and 100 in our array.

Actually we will be seeing if we have 1 in left and 100 in right of 10. Since our list may be something like this

`[90,80,100,10,1]`

Though we can make a triplet of 1,10,100 from the numbers we have. It will not be a valid triplet because 1 comes after 100 and 10. But according to the question, for a triplet i,j,k to become valid index i < index j < index k

That's why when we arrive at number 10. We don't check how many 1s and 100s we have but actually. How many 1s we have to the left of 10 and how many 100s we have to the right of 10.

Now we will iterate every item inside arr.

```
for i in arr:
#do something
```

Initially our index is 0

a gives us count of items to the right of current index

b gives us count of items to the left of current index

**Loop 1**

i == 1, index = 0

First we reduce count of current i from a by 1. a[i]-=1.

Just imagine that you have a list of numbers 1,2,3,4,4 and you have put a finger on top of. Numbers to the left of your finger(3) are 1 and 2 and numbers to the right are 4,4. Since you have put finger on 3 we don't include it. 3 is our current number, so it shouldn't be in a or b. Therefore we subtract it first.

```
>>> a
Counter({1: 0, 3: 1, 9: 2, 27: 1, 81: 1})
>>> b
Counter()
```

1 is not divisible by r=3 therefore 1 can't be center of triplets

No of possible pairs = 0

Now we increase the count of current i in b by 1. b[i]+=1

```
>>> a
Counter({1: 0, 3: 1, 9: 2, 27: 1, 81: 1})
>>> b
Counter({1: 1})
```

**Loop 2**

i == 3, index = 1

First we reduce count of current i from a by 1. a[i]-=1

```
>>> a
Counter({1: 0, 3: 2, 9: 2, 27: 1, 81: 1})
>>> b
Counter({1: 1})
```

Since we have i//3 = 1 in b and i**3 = 9 in a. It means triplet of 1,3,9 is possible.

No of possible pairs = Numbers of 1s in the left of current item * Number of 9s in the right of current item

We have 1 - 1 in b and 2 - 9 in a

Therefore no. of possible pairs of [1,3,9] with current 3 = 1*2 = 3

Now we increase the count of current i in b by 1. b[i]+=1

```
>>> a
Counter({1: 0, 3: 2, 9: 2, 27: 1, 81: 1})
>>> b
Counter({1: 1, 3: 1})
```

Loop 3

i == 9, index = 2

First we reduce count of current i from a by 1. a[i]-=1

```
>>> a
Counter({1: 0, 3: 2, 9: 1, 27: 1, 81: 1})
>>> b
Counter({1: 1, 3: 1})
```

Since we have i//3 = 3 in b and i**3 = 27 in a. It means triplet of 3,9,27 is possible.

No of possible pairs = Numbers of 3s in the left of current item * Number of 27s in the right of current item

We have 1 - 3 in b and 1 - 9 in a

Therefore no, of possible pairs of [3,9,27] with current 9 = 1*2 = 3

Now we increase the count of current i in b by 1. b[i]+=1

```
>>> a
Counter({1: 0, 3: 2, 9: 1, 27: 1, 81: 1})
>>> b
Counter({1: 1, 3: 1, 9: 1})
```

And the loop goes on.

In the end, we just have to add up the no. of possible pairs.

```
If you are still having doubt
Imagine we have [1, 3, 9, 9, 27]
Now put a finger on 1st item
value = 1
value/3 = 0.3333 , value*3 = 3
No of 0.3333 to the left of finger = 0
No of 3 to the right of finger = 1
Possible pairs = 1*0 = 0
Now put a finger on 2nd item
value = 1
value/3 = 1 , value*3 = 9
No of 1 to the left of finger = 1
No of 9 to the right of finger = 2
Possible pairs = 1*2 = 2
Now put a finger on 3rd item
value = 9
value/3 = 3 , value*3 = 27
No of 3 to the left of finger = 1
No of 27 to the right of finger = 1
Possible pairs = 1*1 = 1
Now put a finger on 4th item
value = 9
value/3 = 3 , value*3 = 27
No of 3 to the left of finger = 1
No of 27 to the right of finger = 1
Possible pairs = 1*1 = 1
Now put a finger on 5th item
value = 27
value/3 = 9 , value*3 = 81
No of 9 to the left of finger = 1
No of 81 to the right of finger = 0
Possible pairs = 1*0 = 0
Total possible triplets = 0+2+1+1+0 = 4
```