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.