By Vishal Basumatary in Hackerrank — Jul 3, 2020

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

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

Explanation 1

The triplets satisfying are index , , , , and .

Sample Input 2

5 5
1 5 5 25 125

Sample Output 2

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 i%r == 0:
            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 frequency of each number 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 a center of triplet.

Imagine we have arr = [1, 3, 9, 9, 27] and r = 3

Now put a finger on 1st item
value = 1
Let 1 be the center of a triplet
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 = 3
Let 3 be the center of a triplet
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
Let 9 be the center of a triplet
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
Let 9 be the center of a triplet
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
Let 27 be the center of a triplet
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

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, 3, 9, 9, 27, 81] and you have put a finger on top of 3. Numbers to the left of your finger(3) are 1 and numbers to the right of 3 are 9,9,27,81. 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.

Therefore in our first loop when i == 1

>>> 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 one 1 in b and two 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 one 3 in b and one 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.

Solution in C++

Solution in Python

Subscribe to The Poor Coder | Algorithm Solutions