You've successfully subscribed to The Poor Coder | Hackerrank Solutions
Great! Next, complete checkout for full access to The Poor Coder | Hackerrank Solutions
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Hackerrank - Count Triplets Solution

Hackerrank - Count Triplets Solution

Beeze Aal
Beeze Aal

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++

Count Triplets Solution in C++
You are given an array and you need to find number of tripets of indices such that the elements at those indices are in geometric progression [https://en.wikipedia.org/wiki/Geometric_progression] for a given common ratio and . For example, . If , we have and at indices and . Function Descript…

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