Hey everyone, my name is Kanahaiya Gupta.

Welcome to my YouTube channel. Today, I’m going to discuss Count Triplets hackerrank

problem. But before moving ahead, make sure you have subscribed to my YouTube channel

and click the bell icon so that you don’t miss any update. Let’s start. In this problem you are given an array and

you need to find the number of triplets of indices (i, j, k) such that the elements at

those indices are in geometric progression for a given common ratio r and i

I’m processing any element, it will always be easy for me to look into the leftMap. So,

I know if I’m looking into a leftMap that will always be having the less index from

the ‘a’ and if I am looking on the rightMap that will always be having a greater index from j because we know the constraint of i, j, k,

right. I should be less j and j should be less than k. so if you divide this problem

statement into two, three different parts mid, left and right. So, you’ll never mess

up with the indices. so, you don’t need to check explicitly for the indices whether you

are following that i

now this three is a processing element. when this three is a processing element, how many

‘a/r’ right is there on the left-hand side. So ‘a/r’ is nothing. It is just one, one into

and how many ‘ar’ are there which is nine’s frequency which is three, three, so this is

also three. so far, this three-plus this three, so overall six combinations can be formed.

next, move to the nine here guys, so I’m just moving this. So now, the element will be nine.

So, this is our leftMap and this is our rightMap. Based on that we need to adjust this also

guys. If this is the leftMap, so three frequency we are going to increase, so I have made it

to two. and on the right-hand side, I am going to reduce the frequency to two. If you are

processing nine treating nine as ‘a’. So how many ‘a/r’ exist on the left-hand side ‘a/r’

means nine divides by r (9/3=>3). So how many three exist on this? now, this map will

help guys. How many three exist? two. how you will come to know? because you will do

lookup operation on this. So how many frequencies are there? two. two ‘ar’ exist on the leftMap

and how many ‘ar’ exists on the right-hand side. ‘ar’ is 27. So many 27 are there, will

look into this map One, two into one which is two. so overall, we have three plus three plus

two. So far eight combinations. So now move this cursor to here. So, this time now, this is our leftMap

and this is our rightMap.based on that we have to update this guys, so, now in leftMap

nine is also there. So, this will be, nine with one and here we need to reduce the frequency

of nine. So, here only one frequency. if this is the processing element, how many ‘a/r’

exists two. so, the count will be fetched from this leftMap two into how many ‘ar’ exist

here 27. So, the frequency of 27 is one this is two. so, we will add this, so, overall this right.

So, in a similar way, the next element will process to this nine. So, this is the nine

guys and this is our leftMap. this is rightMap. So leftMap I am going to increase the nine

frequency. this time this will be two and right-hand side we are going to reduce the

frequency of this nine. so, it will be zero now, so how many ‘a/r’ are there in the leftMap? frequency of three will be two. and how many ‘ar’ exist here? ar=27. so, the

frequency of 27 will be one. So, we will add this also. So, we have processed till here. now we’ll move to 27. So now 27 is a processing element guys.

So, this will act as a leftMap and this will be as a rightMap.

When this will act as a leftMap, how many elements are there? one, with one count, three

with two count and nine with three counts, so nine-count will be three, three counts

will be two. and on right-hand side will reduce our 27 count. So, it will become

zero. So, we have only this element in the rightMap. So how many ‘a/r’ is there? So, 27 divided

by 3 which is nine. So how many nine are there in the leftMap. so will go to this leftMap

and see, the frequency of nine is three, into how many ‘ar’ basically 81 are there in the

rightMap. So, in rightMap, 81 frequency is one, so, it’s totally three, so, we have three combination guys because

you can use 9, 27, 81, this 9, 27, 81 and this 9, 27, 81 Right. So now let’s move on

to the last element. So, if the processing element is 81. So, this will come in a leftMap, and this will come in rightMap.basically,

this is nothing. If 27 is a part of leftMap. So, you’re going to enter 27 here with frequency

one and we are going to reduce the frequency of 81 from here because, in rightMap, it does

not exist. So the frequency of 81 will be zero now. So how many ‘a/r’ exist here? 81 divides by

3, which is 27, the frequency of 27 in the leftMap is one into the frequency of 81 into

3, whatever it is, because it doesn’t exist, so it will be zero guys. Because that will

not exist in this map. Right. basically, the 243 doesn’t exist. So, what is the frequency

of that 243, it will be zero. So, one into zero, so it will come as zero. Plus. So now,

if you do this total, you will come to know the number of triplets which can be formed.

So, let’s do a quick total three plus three, six plus two eight plus two, 10 plus two,

twelve plus 3, fifteen. So, the result (total) will be 15 which is our answer. I hope guys, you’ve got the idea of how we

have solved this question. We have processed this array by taking each element as a ‘a’

and taking two different maps. One is the leftMap and one is the rightMap. why we are

doing this guys, just because we do not want to mess up with the indices. you always have

to make sure I should be less than j and j should be less than k. basically, if you are

taking an element which is the form of GP. So, you always have to make sure forming a

GP. we are treating a’s index as j and then it should always be greater than i and this

always should be lesser than k. so we are treating as a middle element and one element

exist on the left-hand side and one element exist on the right-hand side then we are good.

I hope guys, you got the idea. Now let’s see the algorithm in action guys. This is the method guys countTriplets, so

in that we are accepting two parameters, one is a list and second is a common ratio which

is r. So, as we discuss I have taken two maps here one is the leftMap and second is the

rightMap, initially we have filled up the rightMap values. So, I am looping through

complete list guys and storing frequency of each an individual element inside this rightMap.

so, which you can do in your own way guys, what are the programming language you’re using?

what it does? if that element exists, then use the value of frequency of that particular

element and increment by one, else it will be zero. so getOrDefault means default value

of that particular key will be zero if it is not able to find that element in the map.

Okay, basically we are maintaining the frequency count, nothing guys. if you’re not able to

get it. It’s okay. You can implement in your own way, but here just we are calculating

the frequency count, just to get the similarity. Let me show you what you will get after passing

this, rightMap. So, this is what you’re going to

get guys. So, this is the rightMap guys, which you are

going to get after it. So initially you have 1–1, 3–2, 9–3, right? So, the rightMap

we have filled it. So, this is what you’re going to get. So now focus on the pure logic guys. the syntax can be vary based on the language,

but the algorithm will not. So, in this logic, we just maintain that map. Now I’ve taken

a variable count which equals to zero. because in the end, I’m going to return this count.

how many numbers of triplets can be formed? Right? So now I’m processing each an individual

element guy. so, this is the loop for that. And I am taking that element from the list

and calling it as a midTerm. basically, it’s ‘a’ guys. the midTerm is like, in mid whatever

the terms come. So if you’re using a/r, a, and ar so midTerm will be ‘a’.here I’m using

c1 and c3, at the end we are calculating the count. So, this is what c1 and c3 are doing here. But initially, this is the rightMap what we

are doing. whenever we find any element, we are reducing the frequency from the rightMap.

So, this logic will just reduce the frequency guys, you can see minus one. So, if that element

is present in the rightMap, we are reducing the frequency because now that element will

work as a midTerm. So, this is the condition guys where we are checking in the leftMap

whether we have midTerm/r basically ‘a/r’ exist or not? And along with that, guys, we

have to use this modulo operator also. Why? Because midTerm/r this division operator will

not give you a guarantee that midTerm is completely divisible by r. let me show you with the help

of an example. Suppose you have series something like this. If you use this three as a ‘a’

and divide by r. so ‘a/r’ will be one. if you use this four as a ‘a’, 4/3 will be also

equal to one. Because of the integer division, right? which is wrong. That is the reason

you are going to add this condition which will conform if modulo is not a zero it means;

it is not completely divisible because we’re looking at ‘a/r’ which is completely divisible.

so, this cannot be part of the valid triplet. So, that is the reason we have added this

condition. I hope you got it guys. So, when you are checking for the ‘a/r’, we also have

to look if this is true or not? If this is true, it means, it exists in the leftMap.

If it exists, then we are getting the count of this term. So we are storing that count into c1 and from

the right-hand side also we are getting the count of ‘ar’. basically midterm into r.

midterm into r or an into r exist in the rightMap, we are getting the count into a variable which

is c3. Now we have a count from both the side from c1 and from c3 then we are going to multiply

that. Remember guys, let me just show you, so basically guys, this is a c1 and this is

the c3. Let me note it down also here just for your reference. this will be a c1 and

this is c3 guys. and from the leftMap whatever frequency is coming, I’m using as a c1 and

in the rightMap whatever frequency is coming I’m using as a c3. So, once you know that

you are multiplying and which is stored into the count. before moving to the next iteration,

we know, now that particular element which was working as a ‘a’ here that will go as

a part of leftMap. so, the leftMap we are incrementing the frequency of that particular

element. Now for the next iteration, we are doing the same thing, reducing the frequency

from the rightMap.calculating the c1 x c3 and incrementing frequency in the leftMap.

Once we have done with the processing at the end count will maintain the number of triplets

which can be formed from the given array and we are returning that count. just try to run this code guys on hackerrank

platform. So, let me replace this code let’s run this code. so, sample test cases got passed now I’m submitting

this code .so you can see you guys, all test cases got passed. I hope guys, you have enjoyed

it. And if you find this tutorial helpful, please like comment, share and subscribe to

my youtube channel. Thanks for watching, guys.

Hey Every one,

If you find this tutorial helpful, please do not forget to like, comment, share

and It would be great if you can leave your feedback about the tutorial, as I have put a lot of hard work to make things easy for you.

Thanks ..!!

Thanks for this in depth explanation

Very Well Explained. Thank you!