- Count Triplets
- Discussions

# Count Triplets

# Count Triplets

RobertsN + 53 comments Couple of hints:

- Can be done in O(n) -> single pass through data
- No division necessary and single multiplications by R are all that's needed
- Using map(C++) or dict(Java, Python) is a must -> can be unordered map (saves O(logN))
- Try to think forward when reading a value -> will this value form part of a triplet later?
- No need to consider (R == 1) as a corner case

Very interesting problem and it took a while to think it through properly. If anyone is desperate for the code, drop me a message.

seanpearl_rit + 22 comments Thanks, I cleared all the test cases! Takeaways from my solution:

- I used two maps, one to keep count and one to track the number of potential triplets.
- Keeping track of the latter makes updating the result trivial.
- Only a single pass of the array was needed.
- No edge case condition when R is 1.

I highly recommend to anyone not quite understanding, think through the case

5 2 1 2 1 2 4

The expected answer is 3. I was getting 4 with my initial approach. Good luck!

Persistencia + 1 comment Woo, managed to solved it!

Another tip, the order you increment is important!

mhelvens + 0 comments Indeed! That's where

`r = 1`

becomes an edge-case.

JawaharKonathala + 1 comment [deleted]RobertsN + 1 comment 2,0,4 is not in ascending order of position within the array!!!

baymaxlim2204 + 0 comments [deleted]

[deleted] + 0 comments I was also making same mistake as yours. Thanks for the test case

portenez + 0 comments This was the comment that broke my curse. Thank you.

guptavaibhav1991 + 0 comments [deleted]shrikantkarki2 + 1 comment seanpearl_rit can you please put your code here.Coz I am not able to solve it.Mine is taking much more time.

gursahibsahni + 1 comment how is the expected answer 3?

shouldn't it be 4

0 1 4 | 2 3 4 | 0 3 4 | 2 1 4

RobertsN + 1 comment Your last triplet (2 1 4) is not in ascending order within the array. Check the challenge constraints.

nitishkumar_sin1 + 1 comment Dont see any such constraint.

RobertsN + 1 comment Right at the beggining:

"You are given an array and you need to find number of tripets of indices (i,j,k) such that the elements at those indices are in geometric progression for a given common ratio and i < j < k. "

i, j, and k are the indices (positions in the array and they are in ascending order).

ultrarelativist1 + 1 comment i didnt realize that at first, wasnt clear. maybe a comment in the constrains sections such as arr[i] < arr[j] < arr[k] where i

michael_f_fahey + 0 comments [deleted]

sj_enigma + 1 comment Can u please explain this example? I mean how come the asnwer is 3? I am able to count only two triplets consisting of 1, 2 and 4

RobertsN + 2 comments There's three triplets (all consist of the same values but taken from different sets of positions).

first 1 with first 2 and the 4

first 1 with the second 2 and the 4

second 1 with the second 2 and the 4

miloszu + 1 comment and what about second 1 with first 2?

RobertsN + 2 comments Order in the array matters. The second 1 is AFTER the first 2 so you cannot use that 1 and then the 2.

See previous post: https://www.hackerrank.com/challenges/count-triplets-1/forum/comments/491583

c_m_s_gan + 0 comments Thanks for clarifying. This was not explicitly stated in the description.

tomkeane07 + 0 comments [deleted]

avinash_mv + 0 comments This helped me to understand the problem better. Thanks.

nilusfb + 0 comments [deleted]nateshmbhat1 + 3 comments My code works according to the logic shown . Test cases 6 , 11 still fail though . Please tell me whats wrong here....

`HashMap<Long,Long> map = new HashMap<>() ; for(int i =0 ;i < arr.size() ; i++) map.put(arr.get(i) , map.containsKey(arr.get(i))?(map.get(arr.get(i))+1):1) ; long res = 0 ; for(int i= 0 ; i < arr.size() ; i++){ long n = arr.get(i) ; long count = map.get(n) ; Long _1 = map.get(n*r) ; Long _2 = map.get(n*r*r) ; if(_1!=null && _2!=null) res+=_1 * _2 ; map.put(n, Math.max(0,count-1)) ; } return res ;`

amanagarwal2189 + 0 comments did you account for the case where r=1?

maximsadym + 1 comment 5 2

1 2 1 2 4

Expected output is 3, yours is 4

jevvjeeva001 + 0 comments if you sorted your array then you not able to get expected output 3 otherwise if you not sort the array also you meet i

RobertsN + 0 comments You'll come up against the problem of r=1 where you won't get the right answer. That's why my solution (at top) uses 2 maps rather than just one. Also it can be done with a single loop which simplifies the need of the count-1 you're doing near the end.

The main issue I find is that the first loop can populate your map(s) with values which should not be available in the second pass (since they are "further down" the array).

Remember that the order in which values are given is important.

haozhenuk + 0 comments Briliant! Your given case helps me figure out this probelm!

liujiayi19920724 + 0 comments thank you so much! this testcase helped me out!

yagyeshbagaya + 0 comments but in this is not in a sorted manner then how to

nikotian22 + 0 comments Argh I missed the point about i

coderankitkumar + 0 comments Thank you you have made me clear with your algorithm!

lenka_cizkova + 0 comments Thanks, Sean! I've somehow missed the condition and there is not a single test case in the description where this would play any role, so your test case really helped me :)

jack_mason1 + 1 comment I appreciate your insight. I've been trying to integrate your ideas about the problem into a solutions, one of which I hope will eventually pass all test cases.

I have to disagree with your expected response to the the testcase you provided. Per the discription, i, j, and k must be sequential. I believe the answer to your test case should be 1.

Did your solution pass all testcases? I've been able to pass most but I'm timing out.

Jack

RobertsN + 0 comments There's no mention of them being sequential in the problem statement. The mention is that i < j < k, in the sense that the first element of the triplet (i) must come before in the array than the second one (j) and similarly for k. There is no requirement for j = i + 1. If you do code that requirement you will not be able to pass all the testcases.

kevin1kevin1k + 0 comments That's an inspiring hint! Thanks!

shubhamsahu_1501 + 0 comments Can anyone explain how it is 3

Persistencia + 0 comments [deleted]neilsekhon + 2 comments You do need to consider (R == 1)

RobertsN + 0 comments Not with my solution. However it's possible that other solutions do need to take it into account.

Persistencia + 0 comments You should consider it, but you don't need to explicity make a case for it in your code.

preacherr + 0 comments [deleted]sharma71530 + 1 comment I tired your method but it is not working. Can you please share your code so that I can get to know that where did I go wrong?

RobertsN + 0 comments See my reply to my own post.

bhaskar123u + 0 comments [deleted]mishalls765 + 5 comments Why does my code fail with R==1. Or any other hints appreciated.

`static long countTriplets(long[] arr, long r) { HashMap<Long, Long> map1 = new HashMap(); HashMap<Long, Long> map2 = new HashMap(); long count = 0; for(int i = arr.length - 1; i >= 0; i--) { long a = arr[i]; if(map1.containsKey(a*r)) { long c = map1.get(a*r); map2.put(a, map2.getOrDefault(a, 0L) + c); } if(map2.containsKey(a*r)) count += map2.get(a*r); map1.put(a, map1.getOrDefault(a, 0L) + 1); } return count; }`

RobertsN + 1 comment I would try reversing the order of the two ifs in the for loop since you're traversing the array in reverse. For another approach (c++), see my reply to my original post.

mishalls765 + 1 comment Can you explain why interchanging the ifs works?

RobertsN + 1 comment Because you need to test the existence of th value in map2 BEFORE you add to it. If you add "a" to the map and immediately test for "a times r" in the map (when r == 1) you will ALWAYS find it :)

mishalls765 + 1 comment My bad. Now i feel kinda dumb asking about it.

RobertsN + 0 comments You shouldn't feel bad... We all make mistakes and some of mine are real whoppers :)

rajeevpatel + 0 comments if(map2.containsKey(a*r)) count += map2.get(a*r); If above code is moved after long a = arr[i] it will pass all testcases.

SagunB + 0 comments [deleted]nikhilgoyal104a1 + 0 comments Can you please explain the logic here. I am finding it really hard to understand it :-(

muthangyamusyoka + 5 comments Java solution that loops in forward direction. Thanks for the tips

private static long countTriplets(List<Long> arr, long r) { Map<Long, Long> potential = new HashMap<>(); Map<Long, Long> counter = new HashMap<>(); long count = 0; for (int i = 0; i < arr.size(); i++) { long a = arr.get(i); long key = a / r; if (counter.containsKey(key) && a % r == 0) { count += counter.get(key); } if (potential.containsKey(key) && a % r == 0) { long c = potential.get(key); counter.put(a, counter.getOrDefault(a, 0L) + c); } potential.put(a, potential.getOrDefault(a, 0L) + 1); // Every number can be the start of a triplet. } return count; }

The a % r == 0 check is needed for cases where integer division would give a false positive. e.g given [5, 2, 15, 17, 45, 51] and r = 3. At index 3, we have 17 which after integer dividing by 3 we get 5 so that would lead to wrong triplet 5, 17, 51

moustafa_mahran + 0 comments Brilliant !!

owaiskureshi + 1 comment Nice and clean solution,

How this line works ?

if (counter.containsKey(key)....

The counter Map should be empty ?

same confusion related to

if (potential.containsKey(key)...Can you explain please ?

okaieitsme + 0 comments First if of counter checks for (ar^2) in the triplet group and second if for potential checks for (ar).

masterpradip + 0 comments Could you please explain how did you come up with this solution? I want to know the thought process. In some problems I'm finding it difficult to pass all the cases. Do you have any tips for that?

aditya_krp + 0 comments Nice solve. I guess it will make much more sense if you interchange the variable names counter and potential

nieto84 + 0 comments Thanks a lot! I managed to pass the question, but struggled to find an indexing scheme where I didn't have to treat 1 as an edge case. Yours is quite elegant :)

RobertsN + 25 comments #include <bits/stdc++.h> using namespace std; // Complete the countTriplets function below. typedef long long ll; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); long n,r; cin >> n >> r; map<int,long> mp2, mp3; //mp2 to hold count of needed values after this one to complete //2nd part of triplet //mp3 to hold count of needed values to complete triplet int val; long long res = 0; while(n--) { cin >> val; if (mp3.count(val)) //This value completes mp3[val] triplets res += mp3[val]; if (mp2.count(val)) //This value is valid as 2Â° part of mp2[val] triplets mp3[val*r] += mp2[val]; mp2[val*r]++; //"Push-up" this value as possible triplet start } cout << res << endl; return 0; }

billchenxi + 0 comments [deleted]key_destroyer + 2 comments Can you please explain the code?

RobertsN + 11 comments As a base consider a triplet made up of numbers A,B and C (where B = A* r and C = A* r * r = B* r).

For each value (say X) in the array, you have to consider that X may be an A, B and/or C in some triplet.

When can X be a middle of a triplet (that is case X = B in the triplet)? -> when I already have had one or more previous values which will fulfill the requirements of A for this B. So we need to check if there are any previous A's "waiting" for this B. Here we just check the map mentioned in the previous comment. If there's any that means that we need to consider how many A's are "waiting" to know how many 2/3 complete triplets we'd now have with this X.

Similarly to the previous comment we will then let future Cs know that we have these extra 2/3 triplets ready. So store in map of almost complete triplets (ensuring that we add to any previous ones already stored). This is the second part of the loop.

Final case, when X completes one or more previously 2/3 complete triplets. Simply check how many (if any incomplete triplets) are "waiting" for this value to become complete. So check the map of 2/3 triplets and accumulate the result.

In any case X can be an A of a future triplet so add it to the map2 so future B's know of this A's existence -> Final part of the loop.

key_destroyer + 0 comments Awesome! Thanks a lot!!

manoj_banik_cs + 0 comments Excellent !!

fynx_gloire + 1 comment Hello sorry I still don't undersatand. What do you mean this is the second part of the loop? Do you mean the second if statement in the loop? I only see 2 if statements. Can you give a general explanation what each of your maps are doing? I cannot follow your code.

Thx in advance

ddlogesh + 0 comments Hi, this is very simple & very optimised approach. Consider

**mp3**have a count of numbers which may form triplet if the (num * r) is identified once again.Similarly,

**mp2**have a count of numbers which may form doublet if the (num * r) is identified once again.Follow the below 3 steps for every

*num*encountered. So, First, we need to check whether the number*num*is in**mp3**, (i.e)*num*formed triplet or not.- If so, increment the
*count*variable, else directly proceed step-2. - Also check whether (num * r) may form triplet. If so, increment the
**mp3[num * r]**, else directly proceed step-3. - Finally, increment the
**mp2[num * r]**because (num * r) may form doublet in future.

I hope this is helpful!

- If so, increment the

vpontus + 2 comments Java8 solution

static long countTriplets(List<Long> arr, long r){ Map<Long,Long> v2 = new HashMap<>(); Map<Long,Long> v3 = new HashMap<>(); Long count = 0L; for (Long k:arr) { count+=v3.get(k)==null?0:v3.get(k); if (v2.get(k)!=null) v3.compute(k*r,(key,value)->value!=null?value+v2.get(k):v2.get(k)); v2.compute(k*r,(key,value)->value==null?1:value+1); } return count; }

chesschingis + 0 comments White space is a good thing, though I can still make out what you are doing...

Just a personal recommendation.

hectoragr + 7 comments Your solution is very compact, although an alternative is to use Map.getDefaultOr so you don't have to use many null comparions.

static long countTriplets(List<Long> arr, long r) { Map<Long, Long> t2 = new HashMap<>(); Map<Long, Long> t3 = new HashMap<>(); long result = 0L; for(Long a : arr) { result += t3.getOrDefault(a, 0L); if (t2.containsKey(a)){ t3.put(a*r, t3.getOrDefault(a*r, 0L) + t2.get(a)); } t2.put(a*r, t2.getOrDefault(a*r, 0L) + 1); } return result; }

elimon + 2 comments Can you explain what t2 and t3 are for exactly? What are stored in each of their keys and values? I need more elaboration.

dustin_dehaven + 0 comments t2 is a store of the numbers that would serve as the second number in a triplet. For example, if the ratio is 3, if we came across a 9, then 27 could serve as the second number.

t3 is, of course, the number that is being searched for to serve as the third number in a triplet.

learner_i2015 + 0 comments as we know geometric progression is a, a*r, (a*r)*r so on.. here we are using t2 and t3 to track a*r and (a*r)*r respectively .

in t2 we check if element of form a*r is there or not. Similarly in t3 we check if (a*r)*r is there or not. + t3.getOrDefault(a*r, 0L) + t2.get(a)) - part track the no# tupple present .. smart coding!!

oleksii_filonov + 0 comments [deleted]yadavsaloni2018 + 1 comment Thank you for this solution. Got it after a long time. But somehow still failing for corner case r==1. And tracing through, I dont understand how tht is covered here. So wrote an addition check for r==1:

`int len=arr.size(); Map<Long, Long> map2 = new HashMap<>(); Map<Long, Long> map3 = new HashMap<>(); Long val=0L; long count=0; if (r==1) { for (int i=0; i<len; i++) { val = arr.get(i); map2.put(val, map2.getOrDefault(val,0L)+1); } for (Long values: map2.values()){ count+=values*(values-1)*(values-2)/6; //nCr } return count; } for (int i=0; i<len; i++) { val = arr.get(i); map2.put(val*r, map2.getOrDefault(val*r, 0L)+1); if(map2.get(val)!=null) { map3.put(val*r, map3.getOrDefault(val*r, 0L)+map2.get(val)); } count+=map3.getOrDefault(val, 0L); } return count;`

ali_kadum + 0 comments the reason why you need to consider a corner case is of the order of how you call your methods. you should: 1. increase count (if in map3) 2. check if value is in map2 3. add value*r to value map2

codeanit + 0 comments Great solution. Thanks to everyone participating. I had the similar ideas but never though in this way of putting things.

learner_i2015 + 0 comments [deleted]yifanwanghit + 0 comments Well this is a good solution but can't pass all test cases.

radu_harangus + 0 comments Very nice code!

eduasinco + 0 comments That's awesome man

phstkv + 1 comment Hey excellent solution. I initially sorted the array and continued with the logic mentioned above. But two of the test cases fail. I'm using Collections.sort to sort the array. I'm unable to catch as to why the logic would fail if the list is sorted

neeraj_goyal89 + 0 comments Awesome bro :)

sebass27 + 0 comments This is great! Thanks for the explanation about future B and C.

mukeshgupta_mim1 + 1 comment Very Beautifully explained. I am able to visualize and understand now. Thanks Roberts.

vandjk + 0 comments Thank you so much for explaining it beautifully. I could understand this really well

aziz_kudaikulov + 0 comments Very nice!!!

aaron_newton + 0 comments [deleted]

ddlogesh + 0 comments Have a look at this: https://www.hackerrank.com/challenges/count-triplets-1/forum/comments/585514 & try it yourself!

max_waser + 0 comments Brilliant, skimmed through this and instantly the solution latched itself into my mind. Thank you very much!

SagunB + 15 comments Brilliant solution. Helped me a tonne! Equivalent code in python:

from collections import Counter def countTriplets(arr, r): r2 = Counter() r3 = Counter() count = 0 for v in arr: if v in r3: count += r3[v] if v in r2: r3[v*r] += r2[v] r2[v*r] += 1 return count

radialapps + 15 comments Amazing! Looks a bit shorter with defaultdict:

def countTriplets(arr, r): v2 = defaultdict(int) v3 = defaultdict(int) count = 0 for k in arr: count += v3[k] v3[k*r] += v2[k] v2[k*r] += 1 return count

victoria_juan_z1 + 0 comments this is simply amazing. Learning every day from you experts here.

uttugupta316 + 1 comment Can you explain you logic?

RobertsN + 1 comment See my comment 7 posts up (in this thread) or my main post in it's own thread.

uttugupta316 + 0 comments thank you

Bmukhtar + 0 comments amazing solution, spend about 4 hours how to solve

fynx_gloire + 1 comment Hello, I still don't understand the logic. Can you tell me generally what are your v2 and v3 doing?

Thx in advance

mdrafee03 + 0 comments Suppose you have triples x,y,z where the relationship is y = x*r, z = y *r. The trick is that when you first see a number, you consider it x and you know what will be the value of next value x*r, you save it in a dict or map v2. In the next iterations, you will search for the expected number y (x*r), if you find it, similar way you save the next value z = y *r in the v3. So, anything in v3, you know it is your second element. next time, when you see the value you z, you will get your expected triple... it is the way it works suppose 1,3,9,9,27,81 example. In the first iteration there is no value for count and v3, because right side v3[1] and v2[1] doesn't exists, but add 1 to the v2[3] . In the second iteration. you don't have any value for count as v3[3] doesn't exist. But you have v2[3] from previous iteration. So, now v3[9] = 1 and v2[9] = 1. so, the value v3[3] means you got 2 value for your triple. In the third iteration, count is 1 as you v3[3] has value from previous iteration and the triple are completed. Similiarly next moves are continued if you still don't understand, just print(k, v3, v2) at the end of your for loop, you will see the changes of each iteration and make sense.

boiko_ivan + 0 comments Truly amazing... I spent 6 hours and got through all the test cases with O(n) and special treatment of r=1. But I was nowhere near this simplicity. Need to spend another few hours to understand it.

dancastellani + 1 comment brilliant!

jereini + 0 comments Its pretty awesome

it_henrik + 0 comments not just looks shorter, it also runs significantly faster :)

hamed_h_rafati + 0 comments How did you come to this solution? it's working but i am struggling to understand the logic. Where is the logic of

**Triplets**?libinngeorge + 1 comment Added some comments and explanation.

def countTriplets(arr, r): # stores number of tuples with two elements that can be formed if we find the key potential_two_tuples = defaultdict(int) # stores number of tuples with three elements that can be formed if we find the key potential_three_tuples = defaultdict(int) count = 0 for k in arr: # k completes the three tuples given we have already found k/(r^2) and k/r count += potential_three_tuples[k] # For any element of array we can form three element tuples if we find k*r given k / r is already found. Also k forms the second element. potential_three_tuples[k*r] += potential_two_tuples[k] # For any element of array we can form two element tuples if we find k*r. Also k forms the first element. potential_two_tuples[k*r] += 1 return count

jayjunkyu + 0 comments I still don't get it. God help me.

pranayshahxyz + 0 comments Wow.

mdrafee03 + 0 comments Best, Excellent

whoan + 0 comments I wanted to explain how I understood your solution in a comment but I thought it deserved a whole blog entry.

Thanks for your elegant solution.

bpf212 + 0 comments Superb

kepemey119 + 0 comments Thank you... explained very well, I am able to visualize and understand now.

VAMSINADH + 0 comments what are v2 and v3 there

bays123 + 0 comments [deleted]angelopolotto + 3 comments I solved using the python build in dictionary, more code but more easy for beginers:

`def countTriplets(arr, r): # initialize the dictionaries r2 = {} r3 = {} count = 0 # loop throgh the arr itens for k in arr: # if k in r3 indicates the triplet already completed, # the count need be incremented if k in r3: count += r3[k] # if k in r2, it is the secound number of the triplet, # your successor (third element k*r) need be added or incremented in the r3 dict # because is a potencial triplet if k in r2: if k*r in r3: r3[k*r] += r2[k] else: r3[k*r] = r2[k] # else, k is the first element of the triplet, so, # your seccessor (secound element k*r) need be added or incremented in the r2 dict # because is a potencial triplet if k*r in r2: r2[k*r] += 1 else: r2[k*r] = 1 return count`

sidhumeher1 + 0 comments Thank you for the explanation through comments

shatabdi07igit + 1 comment your code is of complexity o(n^2)

RobertsN + 0 comments Beg to differ.

ciprian_42 + 0 comments I had some difficulties understanding this problem, but your code and explaination made it crystal clear. Thank you!

fynx_gloire + 1 comment Hello, I still don't understand the logic. Can you tell me generally what are your r2 and r3 doing?

Thx in advance

RobertsN + 0 comments

eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 2 comments For me the division approach is more intuitive:

def countTriplets(arr, r): r1 = Counter() r2 = Counter() count = 0 for v in arr: if v/r in r2: count += r2[v/r] if v/r in r1: r2[v] += r1[v/r] r1[v] += 1 return count

RobertsN + 1 comment However you run into the possibility of straight division (/) giving you the wrong answer (or actually using floating point values when they are not necessary). Also consider that division is

*much more expensive*in computing terms than multiplication. I'm glad however, that you were able to solve it. Unfortunately HR is not currently (as far as I know) showing processing times (so you could maybe compare to other solutions). I always try to reduce both memory and processing times to a minimum.eduasinco + 0 comments That's true you are totally right, great solution ;)

sgrebenkin + 0 comments Agree, more intuitive. Had the similar solution.

cpagravel1 + 0 comments [deleted]RajeshKumar2020 + 0 comments [deleted]amittai_aviram + 0 comments [deleted]advaithsurya + 0 comments Can you please explain this code? r2 and r3 are basically empty objects for a Counter class. Okay. Got it. We are then iterating through arr. Okay . But, What is (if v in r3) mean? r3 does not have anything right? It is just an object !

saket_suraj57 + 0 comments Here r3 is empty then how (if v in r3:) is working?

kindresh44 + 0 comments Awesome

jgrandydev + 1 comment RobertsN solution doesn't work for test case 3 ( r = 1 with very long list of identical numbers ) and I can't figure out why not.

RobertsN + 2 comments It passed all test cases for me and I cannot think why it shouldn't with r==1 and a very long list of (repeated) values. Combinatorics would be unnecessary since each value is processed individually (so there's no need for a (n)*(n+1) /2 )

However if you're going over the long maximum you'd need to change the maps to long long (and probably change res to __uint128_t)

Can you post or link such a test case? The solution appears to have helped other implementations (above python's being an example) and no problems other than your's have been reported yet.

jgrandydev + 1 comment I'm brand new here and not sure how to link to test cases.

On my screen it's Testcase 3 :

`Input (stdin) 100000 1 1237 1237 1237 1237 1237 1237 1237 1237 etc Expected Output 166661666700000 Compiler Message Wrong Answer`

There's no stack trace and the wrong answer is not listed.

`C# int 2,147,483,647 C# long 9,223,372,036,854,775,807 expected answer 166,661,666,700,000`

All 12 other test-cases passed. I'm totally baffled.

RobertsN + 2 comments My successful submissions (C++14 and Python3) all got 166661666700000 (that's why I used a long long) for an answer on test case 3 (had to buy the TC since although I passed all I still get charged the 5 hackos :( ).

Maybe some problem with the mono compiler for c# on HR?

I'll try making a c# submission to see what happens.

RobertsN + 3 comments Clears all testcases. Could have also used TryGetValue and save some ifs

static long countTriplets(List<long> arr, long r) { var mp2 = new System.Collections.Generic.Dictionary<long,long>(); var mp3 = new System.Collections.Generic.Dictionary<long,long>(); long res = 0; foreach (long val in arr) { if (mp3.ContainsKey(val)) res += mp3[val]; if (mp2.ContainsKey(val)) if (mp3.ContainsKey(val*r)) mp3[val*r] += mp2[val]; else mp3[val*r] = mp2[val]; if (mp2.ContainsKey(val*r)) mp2[val*r]++; else mp2[val*r] = 1; } return res; }

jgrandydev + 1 comment yeah once I switched to long everywhere my solution passed all TCs

marc_spraragen + 0 comments This was exactly my problem (and solution!) too. Thanks!!

shahareh + 1 comment Hi, I cant understand something: This is worked for me only when I'm trying to provide a sorted array, like this: [ 1,1, 5, 5, 25, 125] - res is 6, but when the array is not sorted like this [ 1, 5, 5, 25, 125, 1] the result is difference - 4. It passed a test with unsorted array, so what am I missing here? Why is the order matter? Thanks!

Update: Just noticed that the order of the triplet is matter, and that the order of the triplet (i,j,k) must implement i < j , k.

RobertsN + 0 comments Yep, the order of the values in the array IS important. Sorting the array will mess up your results :)

martindevillers + 0 comments Brilliant solution. Also I feel this one was definitely well above "medium".

jc_imbeault + 1 comment I'm confused by the expected result. For a list of repeated (identical) number, the answer should be 0 no?

If the input is (for example):

3 1 1 1 1

There is no geometric progression.

RobertsN + 0 comments If the ratio (R) is one, then the answer definitely IS a geometric progression (albeit rather simple). For the test case you give the correct output is 1.

sadstatue128 + 0 comments Thank you! Changing int to long worked for me on C#.

edmondo_porcu + 1 comment Can you please explain what you mean as "2nd part of the triplet" and how do these indexing relate to the one in the Java version above?

RobertsN + 1 comment A triplet is three values with a common ratio of R. So we have triplet: A,B,C

A is the first part, B is the middle part, C is the final part of the triplet.

B = A * R

C = B * R = A * R * R

The "indexing" is actually a hashmap (a.k.a. dictionary) - saves space rather than a huge array holding count values.

For further details check the 4th post in this thread.

edmondo_porcu + 1 comment My question wasn't clear, apologies: * When you say "2nd part" are you saying B and C , is that correct? * When I mention the indexing, I see two solution : one that use the current value to access the access map (yours in C++) and one that uses current_value * R, the one in Java. Why are the two equivalent?

RobertsN + 0 comments By second part of the triplet I'm referring to the B part.

In this thread at least there's no java version, just my C++, a couple of Python and a C# (also mine). I haven't checked the whole forum for a Java version.

Maybe check https://www.hackerrank.com/challenges/count-triplets-1/forum/comments/474943 (4th post for this thread) for a detailed explanation. This doesn't actually mean all implementations follow this. Some of the other solutions process the array in reverse and are equally valid.

I use the current value x to check if it's a possible C to a (possibly multiple) set of A's and B's already seen. If so I accumulate these new triplets.

I the use the current value x to check if it's a possible B to previously seen A's. If so I add this to possible future C's which might need this B to complete triplets.

Finally whatever the value of x is it's always a possible A of a triplet so I ensure that future B's will find it.

himanshu_1 + 2 comments I used the same logic but it failed on 6th test case. Can you please tell me where is the problem?

long int n=arr.size(),count=0;

`unordered_map<long int ,long int> mp1,mp2; for(long int i=0;i<n;i++){ if(mp2[arr[i]/r]!=0){ count+=mp2[arr[i]/r]; } if(mp1[arr[i]/r]!=0) mp2[arr[i]]+=mp1[arr[i]/r]; mp1[arr[i]]++; } return count;`

RobertsN + 0 comments Dividing instead of multiplying? Don't forget, also, even if you reverse the logic that INTEGER division rounds (down) your result (meaning 5/2 = 2, not 2.5). This will lead to finding triplets which aren't really correct (say 2,5,25 with r=2).

iamakshatjain + 0 comments You just need to put a modulus condition. Divide only when the arr[i]%r is zero. Else the elements( arr[i]/r ) may clash i.e, for instance, 5.5 and 5 would be considered same.

tiberiu_iancu + 0 comments I feel so dumb after spending so much time on the problem, yet the solution was so simple. Thanks!

rodobros + 0 comments Really brillant solution. Thank you

sgrebenkin + 0 comments I came up with pretty same solution, less performant (division), but more intuitive from my point of view.

`#include <bits/stdc++.h> #include <map> using namespace std; int main() { long n, r; cin >> n >> r; long res = 0; map<long, long> m0; map<long, long> m1; while (n--) { long x; cin >> x; if (x % r == 0 && m1.count(x / r)) res += m1[x / r]; if (x % r == 0 && m0.count(x / r)) m1[x] += m0[x / r]; m0[x]++; } cout << res; return 0; }`

nmckillip1 + 0 comments [deleted]peterwen0127 + 0 comments God's work. Thanks a lot!

luisgerardoangel + 0 comments Same solution but in JS

function countTriplets(arr, r) { let mp2 = {}; let mp3 = {}; let count = 0; arr.forEach(val => { if(mp3.hasOwnProperty(val)) count += mp3[val]; if(mp2.hasOwnProperty(val)) mp3[val*r] = (mp3[val*r] += mp2[val]) || mp2[val]; mp2[val*r] = (mp2[val*r] += 1) || 1 ; }); return count; }

ara_hovakimyan + 2 comments My Solution. Now I need to understand the difference between these solutions.

// Complete the countTriplets function below. long countTriplets(vector<long> arr, long r) { long count = 0; map<long, long> m1; map<long, long> m2; for (const auto &e : arr) { if (e % r == 0) { count += m2[e / r]; m2[e] += m1[e / r]; } ++m1[e]; } return count; }

ara_hovakimyan + 1 comment More simple solution.

// Complete the countTriplets function below. long countTriplets(vector<long> arr, long r) { long count = 0; map<long, long> m1; map<long, long> m2; for (const auto &e : arr) { count += m2[e]; m2[e * r] += m1[e]; ++m1[e * r]; } return count; }

iamnagaky + 0 comments This works like a charm!

RobertsN + 1 comment Rounding on division will give wrong results.

ara_hovakimyan + 1 comment Was used operator "%" to check the division without residue(balance).

ara_hovakimyan + 0 comments A beautiful solution suggested by rishi_07 which can be found in section Editorial.

vladgets + 0 comments Beautiful solution!

backd00red + 0 comments This solution is brillant... Just chapeau!

Spleen + 0 comments Hi ! I'm searching for better solutionâ€¦ butâ€¦ Really nice !

P.S : 1/ I suggest to test with bool returns values like this : (mp3.count(val) != 0u) and (n-- > 0)

2/ use nullptr instead of NULL.

3/ "using" instructions instead of typedef in C++11

thetantrik + 0 comments BEAUT. Thanks a lot man

rounaknayee007 + 1 comment your code doesnt work for this test case 5 125 125 125 25 5

the output should be 1 but your code prints 0

jc_imbeault + 1 comment You are correct but ... what the problem description doesn't state is that the input is always ordered.

In other words 5 125 125 125 25 5 is not a 'valid' input.

This problem needs to have it's description fixed.

RobertsN + 0 comments The problem statment DOES mention that position within the array IS important. There's no mention of input ordering in that numbers may come in any order and are not necessarily ordered. Therefore you must consider the array unordered and as mentioned before this DOES NOT mean to say you have to order it but it DOES mean to say "take them in the order they are".

nikolay_dimitrov + 0 comments [deleted]Talii + 0 comments Nice!

harry_hummel + 0 comments [deleted]aaron_newton + 2 comments I find it helped to alias

`mp2`

as`neededForDoublets`

and`mp3`

as`neededForTriplets`

. Once I did this, the logic clicked. Given the value 2 for this iteration with an`r`

of 3, we'd need a 6 (2 * r) to form doublet(s). If we find that 6 in a subsequent iteration, then we increase the possible number of triplets for 18 (6 * r) by the - now known - number of doublets - (2, 6). We need an 18 here people! If we find 18 on a subsequent iteration, we now know we have the triplets we flagged as possible in the previous step, so we can add them to the triplet count.RobertsN + 0 comments Your comment is absolutely valid. I sometimes use rather cryptic variable names because I know that this is not production code and I'd rather type less. Aliasing (or even replacing) the variables makes it a lot easier to understand.

aymen_ayadi1 + 0 comments maybe the easiest explanation in all above this discussion.

sproutd + 0 comments Wow, thanks a lot man :)

rjoudrey + 0 comments [deleted]himanshusurana11 + 1 comment Help...

RobertsN + 0 comments Check: https://www.hackerrank.com/challenges/count-triplets-1/forum/comments/468507 and later comments... :)

rosamohammadi + 0 comments this feels more like a hard problem > . < thanks for posting. glad i came across this.

denis631 + 0 comments The idea of using 2 hash map pointed me into the right direction, thank you :)

jhwoodyatt + 0 comments It was only after my first C++ solution passed all the test cases that I saw this comment in the discussion. It prompted me to refine my solution to eliminate the division and modulo operations. It seems necessary to make a small addition to the linear space factor to do so, and whether that extra space is worth the arithmetic complexity reduction seems like a weird trade-off in an algorithm that uses standard allocators.

chilicoder + 3 comments after your hint made this Javascript solution

function countTriplets(arr, r) { let dict = {}; let count = 0; arr.forEach(val=>{ if (!dict[val]) {dict[val] = {s1:0,s2:0,s3:0};} if (!dict[val*r]) {dict[val*r] = {s1:0,s2:0,s3:0};} count += dict[val].s3; r===1 ? dict[val].s1 = 1 : dict[val].s1 += 1; dict[val*r].s3 += dict[val].s2; dict[val*r].s2 += 1; }); return count; }

jhwoodyatt + 0 comments Now that's nice.

dustin_dehaven + 0 comments This line doesn't do anything and can be removed:

r===1 ? dict[val].s1 = 1 : dict[val].s1 += 1;

jdtorregrosas + 1 comment You could achieve this with .reduce

function countTriplets(arr, r) { let count = 0; arr.reduce((acc, val) => { if (!acc[val]) { acc[val] = { s1: 0, s2: 0, s3: 0 }; } if (!acc[val * r]) { acc[val * r] = { s1: 0, s2: 0, s3: 0 }; } count += acc[val].s3; acc[val * r].s3 += acc[val].s2; acc[val * r].s2 += 1; return acc; }, {}); return count; }

burnandbass + 0 comments Or minify it even more:

return arr.reduce( ([dict, count], val) => { !dict[val] && (dict[val] = [0, 0, 0]); !dict[val * r] && (dict[val * r] = [0, 0, 0]); count += dict[val][2]; dict[val * r][1] += 1; dict[val * r][2] += dict[val * r][1]; return[dict, count]; }, [{}, 0] )[1];

starcs_of_north + 0 comments [deleted]kerryjones21 + 1 comment These hints were great but I'm not sure what you were referring to with map(dict) -- I didn't use any mapping at all.

RobertsN + 1 comment Dict (is for dictionary, i.e. python which also can be Counter) whilst in C++ it's called map.

kerryjones21 + 0 comments Make sense, I thought you were referring to the python map() function used

*on*a dictionary

kamanashisroy + 0 comments I ran a forward loop to find number of geometric-predecessors of each position in O(n) time.

Then I ran one last backward loop in O(n) time to find the number of geometric-successor of each position and adding the product of num predcessor and num successor to get the final result.

laryho18 + 2 comments Hi please my code fails at test case 6 (not R ==1), any hints would be appreciated.

public static long countTriplets(List<Long> arr, long r) { HashMap<Long, Long> v1 = new HashMap<>(); HashMap<Long, Long> v2 = new HashMap<>(); long count = 0; for (Long digit : arr) { if (v2.containsKey(digit / r)) { count += v2.get(digit / r); } if (v1.containsKey(digit / r)) { long c = v1.get(digit / r); v2.put(digit, v2.getOrDefault(digit, 0L) + c); } v1.put(digit, v1.getOrDefault(digit, 0L) + 1); } return count; }

hectoragr + 2 comments Hi,

Most people agree that even though division is the intuitive way to solve this, it is better to use multiplication. So, as opposed to looking back in the map to see that you have already processed the two previous triplets, at each step you calculate if you are one of the "next" triplets 1) If you are the third triplet you increment the count in how many times you are expected (the value in the map for 'k' 2) If you are expected as 'j' (second triplet), calculate the expected k and add 1 to the map of expected k 3) Whatever value you are, add yourself times r as the expected 'j'

long result = 0L; for(Long a : arr) { result += t3.getOrDefault(a, 0L); if (t2.containsKey(a)){ t3.put(a*r, t3.getOrDefault(a*r, 0L) + t2.get(a)); } t2.put(a*r, t2.getOrDefault(a*r, 0L) + 1); } return result;

Your code is not wrong, but perhaps the long division is not working as you expect it for one single value in the 100000 values for case 6.

Hope this helps!

laryho18 + 2 comments Thanks a lot! I used the division cuz i found it hard to understand the forward multiplication thingy, I guess I just have to study it more. Thanks again though.

hectoragr + 0 comments No problem!

gersonsosa1 + 0 comments I really was breaking my head about this same part of the solution and turns out it's quite simple, if division works very easy with going forward from 1 to n, then multiplication works the other way around.

leospostbox + 0 comments Took me 3 hours to figure out why Test case 6 was failing. Thank you SOOOO much for tip. This was indeed the case. I switched integer to float devision (python) and use floats everywhere, now it works as expected).

bob_perry + 0 comments I encountered the same issue (only test case 6 failing). The root cause issue is that integer division can give the same answer for multiple different numerators. For example, the numerators 10, 11, 12, 13, and 14 all give the same answer when dividing by 5. For every number that you encounter, you want to keep track of the fact that you have encoutered that number. However, only numbers that are either 1 (in the edge case that r == 1) or are cleanly divisible by r (i.e., n % r == 0) should be considered as candidates to be j or k in the triple (i, j, k).

ding_randy + 0 comments Thanks for the hints! Still had to struggle for a while after taking them in but managed to solve this problem eventually.

I read some other comments saying they used two maps but I also arrived at a correct solution using one map.

gersonsosa1 + 0 comments This took me a while, after all all your hints were very helpful, I just would add that you have to count instead of "keep track" to meet the performance requirements, and just 1 map is enough to get to the correct solution.

lwchkg + 0 comments According to the constraints, multiplication may cause integer overflow in 32-bit platforms.

akash0744 + 0 comments I need a C code?

guglanimk + 0 comments Found your hints to be extremely helpful. Thanks for not putting the code here as it got me thinking and coming up with a solution. I still have 4 test cases that are timing out but getting much closer.

winnochan + 0 comments Thanks for your hints. I have to consider (r == 1) with my solution. How to optimize my solution so that I don't need to consider the corner case. Looking forward to your reply!

def countTriplets(arr, r): singleMap = {} doubleMap = {} tripleMap = {} for num in arr: # every number in this array can be the first number of triplets singleMap.setdefault(num, 0) singleMap[num] += 1 # if it can be the second number of triplets if num % r == 0: first = num // r if first in singleMap: doubleMap.setdefault((first, num), 0) doubleMap[(first, num)] += singleMap[first] if num % r == 0 and num % (r * r) == 0: # it can be the third number in the triplets first, second = num // r // r, num // r if (first, second) in doubleMap: tripleMap.setdefault((first, second, num), 0) tripleMap[(first, second, num)] += doubleMap[(first, second)] if r == 1: return sum(map(lambda n: n * (n - 1) * (n - 2) // 6, singleMap.values())) return sum(tripleMap.values())

Nopethisis + 0 comments #include<bits/stdc++.h> using namespace std; typedef long long int l; int main() { std::ios_base::sync_with_stdio(false); l n,r,i; cin>>n>>r; l arr[n]; map<int,int> count; map<int,int> track; for(i=0;i<n;i++) { l a; cin>>a; arr[i]=a; count[a]++; } l ans=0; for(i=0;i<n;i++) {//cout<<"\ncoubt of "<<arr[i]<<" is"<<count[arr[i]]; count[arr[i]]--; // removig the one occurence of the element if(arr[i]%r==0) { l a=track[arr[i]/r]; l b=count[arr[i]*r]; ans=ans+a*b; } track[arr[i]]++; // adding the element to second map so that we could keep //the track on previous element like 1 3 9// we are simply storing 1 as a previous //element } cout<<ans; } How about this code?

nankero94 + 0 comments thanks, you were a big help.

earthshakira + 0 comments Thanks for the hints, worked like a charm

huangkewei + 0 comments Brilliant!!

lalithnani + 1 comment can you share the code??

bonnotguillaume + 0 comments In fact, you need to consider r == 1, this hint made me loose a lot time :(

Test case 2, 3, 11 are with r == 1

In think what they meant, is that there is a solution where you dont need to do : if(r == 1)

idriskas + 1 comment It keeps timing out. I understand my solution is cubic but how do i get it faster.... :(

Here is my solution:

import java.io.

*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList;public class Solution {

`// Complete the countTriplets function below. static long countTriplets(List<Long> arr, long r) { long result = 0; Map<Long, Map<Long, Long>> triplet = new HashMap<>(); Map<Long, Long> pairProgression = new HashMap<>(); Map<Long, Long> placeHolder = new HashMap<>(); long pH = -1000; long secondValue = -1000; long thirdValue = -1000; triplet.put(pH, placeHolder); for(long i = 0; i < arr.size(); i++){ secondValue = -1000; thirdValue = -1000; int firstValueIndex = (int) i; long firstArrayValue = arr.get(firstValueIndex); //System.out.print("First Values : "+firstArrayValue); for(long j = i + 1; j < arr.size() ; j++){ int secondValueIndex = (int) j; long secondArrayValue = arr.get(secondValueIndex); long secondValueExpected = firstArrayValue * r; if(secondArrayValue == secondValueExpected ) { for(long k = j + 1; k < arr.size(); k++){ int thirdValueIndex = (int) k; long thirdArrayValue = arr.get(thirdValueIndex); long thirdValueExpected = secondArrayValue * r; // System.out.println(firstArrayValue); // System.out.println(secondArrayValue+" "+secondValueExpected); // System.out.println(thirdArrayValue+" "+thirdValueExpected); // System.out.println(" "); if(secondArrayValue == secondValueExpected && thirdArrayValue == thirdValueExpected){ Map<Long, Long> pair = new HashMap<>(); pair.put( j, k); triplet.put(i, pair); result++; } } } } } // For iterating through array - IK // for (Map.Entry<Long, Map<Long, Long>>entry : triplet.entrySet()) { // Long key = entry.getKey(); // System.out.println(key); // } //System.out.println(r); return result; } public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); String[] nr = bufferedReader.readLine().replaceAll("\\s+$", "").split(" "); int n = Integer.parseInt(nr[0]); long r = Long.parseLong(nr[1]); List<Long> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" ")) .map(Long::parseLong) .collect(toList()); long ans = countTriplets(arr, r); bufferedWriter.write(String.valueOf(ans)); bufferedWriter.newLine(); bufferedReader.close(); bufferedWriter.close(); }`

}

RobertsN + 1 comment Have a look at the various solutions already posted in this forum. It can be done in either O(N) - arguably (depends on the implementation of maps/hashmaps) - but definitely in O(NlogN). You're doing various repeating passes through the array when only one is necessary. Regards.

idriskas + 0 comments none of them are in java can you oermalink a java solotuok that is readbale ?

krista_krista + 0 comments Here's a JavaScript solution based on RobertsN's excellent idea.

const triplets = (arr, r) => { let r2 = {}; let r3 = {}; return arr.reduce((c, v) => { if (r3[v]) { c += r3[v]; } if (r2[v]) { r3[v*r] = (r3[v*r] || 0) + r2[v]; } r2[v*r] = (r2[v*r] || 0) + 1; return c; }, 0); }

mayankmaheshwar2 + 0 comments please provide link

officialkeval98 + 1 comment want cpp code

RobertsN + 0 comments Have you checked the threads? It has already been posted.

kgm1995 + 0 comments 100% accurate guidance. Really helpful. Thanks a lot. Some more hints: - 2 dict/map use helps it get easier. - order in which you update your dict determines whether to consider r=1 as corner or not.

utsav_krishnan + 0 comments Took a lot of time to figure out the O(n)-time O(n)-space solution, no corner cases, very simple code. At the end it's very beautiful.

alfredo_starace + 1 comment I can't figure out what I'm doing partially wrong. I mean I cleared all the cases, but I had to consider r==1 as a special case:

`HashMap<Long, Long> counter2 = new HashMap<Long, Long>(); HashMap<Long, Long> counter3 = new HashMap<Long, Long>(); long tot = 0; for (Long elem : arr) { counter2.put(elem * r, counter2.getOrDefault(elem * r, 0l) + 1l); if (counter2.containsKey(elem)) { counter3.put(elem * r, counter3.getOrDefault(elem * r, 0L) + counter2.get(elem)); } tot += counter3.getOrDefault(elem, 0L); } if (r == 1l) { Long tot_r1 = 0l; for (Long count : counter2.values()) { tot_r1 += count * (count - 1) * (count - 2) / 6l; } return tot_r1; } return tot;`

How do you avoid the r==1 case?

alfredo_starace + 0 comments Ok , I figured it out, it's also the order of the operations that matters, 1st update tot, then counter3, and last counter2, so it should be instead:

`tot += counter3.getOrDefault(elem, 0l); if (counter2.containsKey(elem)) { counter3.put(elem * r, counter3.getOrDefault(elem * r, 0L) + counter2.get(elem)); } counter2.put(elem * r, counter2.getOrDefault(elem * r, 0l) +1l);`

agsigner + 0 comments Thank you. I hadn't realized the arrays were not sorted (need to stop assuming things when it's not stated!) After a point - I gave up on trying to look for, and keeping record of numbers...and start keeping track of sequences. That worked much better!

zhaohuabing + 1 comment I came up with the solution with two maps, one to track the potentail Triplets with the first one element matched and one to track the potential Triplets with the first two elements matched, but my code failed with the R==1 edge case. Could any one help me with that?

RobertsN + 0 comments The order in which you update the maps and track count of completed triplet is important. My order: Update completed triples count (add to final result). Update map with 2 elements Update map with 1 element.

shashank_shukla4 + 0 comments [deleted]yagyeshbagaya + 1 comment please help me can I solve this question without using map i suffer the problem of time

RobertsN + 1 comment Dear yagyeshbagaya,

Then use maps!!!

If not, the tutorial has a different solution (which is arguably of the same complexity of my answer but I would believe somewhat slower). Please do feel free to test alternative -> that is what makes HackerRank interesting.

You could investigate replacing maps with an array of count values but I would assume you'd exceed space restrictions.

Kind regards.

yagyeshbagaya + 0 comments that's okay I face the problem of time complexity in every question do you have any strategy to reduce the complexity this is very

orange_kao + 0 comments [deleted]abhisharma3187 + 0 comments Hi, can you help me what i am missing in below code as only 4 cases are failing.

# include

using namespace std;

int max(int a,int b,int c) { int temp=0; if(a>b) { temp=a; } else { temp=b; } if(temp>c) { return temp; } else { return c; } }

// Complete the countTriplets function below. long countTriplets(int arr[], int r, int n) { map mp; for(int i=0;i

`int m=mp.size(), res=0; if(r==1) { res=((mp[1])*(mp[1]-1)*(mp[1]-2))/(3*2); } else if(m>2) { for(int j=0;j<m-1;j++) { // cout<<mp[pow(r,j)]<<" "; if(mp[pow(r,j)] && mp[pow(r,j+1)] && mp[pow(r,j+2)]) { res=res+(mp[pow(r,j)]*mp[pow(r,j+1)]*mp[pow(r,j+2)]); } else { continue; } } } else { return 0; }`

return res; }

int main() { int n,r; cin>>n; cin>>r; int a[n]; for(int i=0;i>a[i]; } long b=countTriplets(a,r,n); cout<

Also, can you share you code with proper explaintation.

Thanks in advance:)

nphs2wb + 0 comments Thanks for the hints. It took me lots of submissions to get it right though. What a clever way to solve this problem.

semisonic + 0 comments There is at least one test case which specifically tests for r == 1. So this is a corner case which clearly has to be considered

arici_edu + 0 comments below code is giving runtime error? def countTriplets(arr, r):

`my_list = [] for i in arr: my_list.append(int(math.log(i,r))) comb = list(combinations(my_list,3)) counter = 0 for i in comb: if (i[0]==i[1]-1==i[2]-2): counter += 1 return counter`

learner007 + 0 comments amazing thoughts

suryan0800 + 0 comments Thank you for the Tips bro.

C6H9N3O3 + 0 comments Another approach that resembles the popular one here. It enumerates the array backward and builds an imaginable graph of connections

*a --> a*r --> a*r*r*. But instead of building an actual graph it just accumulates statistics of nodes connections. That approach takes O(N), too, but utilizes a single map only! R = 1 is processed in a general way, too. C++14 code is down below:long countTriplets(vector<long> arr, long r) { long total = 0; map<long, pair<long, int>> stats; for (auto it = arr.crbegin(); it != arr.crend(); ++it) { long child_transit; int child_own; tie(child_transit, child_own) = stats[*it*r]; long our_transit; int our_own; tie(our_transit, our_own) = stats[*it]; stats[*it] = make_pair(our_transit + child_own, our_own + 1); total += child_transit; } return total; }

sumanth_pudi + 0 comments [deleted]jvgagliardi + 0 comments Great explanantion!

manndras + 11 comments Took me forever to figure this out. It's a really cool problem - the breakthrough came when you realize that, since sequentiality is important, then the array should be walked in reverse because the only values you want to check are those at higher indeces than the one you are checking.

The other big thing to realize is that you're checking for two things, not just one - you're checking for the existence of a value r times the current value, or your checking for a pair that exists for the for the value that begin at r times the current value and also contain r times that value.

For example: Let's say r is 3. If you have a the value you're checking while iterating the array that is also 3, and there's a 9 and a 27 in the dictionary that you've been populating, you should have populated another dictionary and entry for the pair of the values (9, 27) because those are a pair where 27 is r times 9 and if we find a 3 at a lower index, then we know we have a triplet.

So the algorithm is: -- keep two dictionaries: 1. a dictionary to store the number of times each single value that is repeated in the array 2. a dictionary to store any pair of values that are i and (i * r) (using i as the key)

-- Walk the array backwards 1. if the pair dictionary has a value for r times the one you're checking, then you add the number of pairs to the overall count. 2. otherwise, if there's add a new pair and add it to the pair dictionary if there's a value r times the one you're checking in the single value dictionary. 3. otherwise, just add the value to the single value dictionary.

And that will do it.

In Python, O(N) time complexity:

`def countTriplets(arr, r): count = 0 dict = {} dictPairs = {} for i in reversed(arr): if i*r in dictPairs: count += dictPairs[i*r] if i*r in dict: dictPairs[i] = dictPairs.get(i, 0) + dict[i*r] dict[i] = dict.get(i, 0) + 1 return count`

RobertsN + 0 comments Interesting approach. Different to mine but definitely interesting.

augusts + 0 comments it's actually similar as mine, but from different direction. you solution didn't need to handle the case arr[i] % r != 0, which I fell in for a while.

aaha97 + 2 comments This solution, like many others, claims to be O(n) because there is only one 'for' loop involved. But that idea is totally flawed because, the access in dictionary (or STL maps in C++)is O(log(n)). This means the overall worst case complexity when all the elements are distinct, is O(nlog(n)).

manndras + 1 comment Dictionary access for all operators used here is O(1), not O(log n). https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

aaha97 + 1 comment I didn't know this. Thank you. But here is something I read.

https://stackoverflow.com/a/1963514

So, in a worst case scenario, the operation may be O(n). This makes the python implementation solution O(n^2).

vijaychavda + 1 comment You need to understand how a hashmap internally works, especially in case of collisions.

In most cases, the hashmap maps to a list (or another hashmap!) of values that fall under the same keys. Collisions are rare for small data-sets. And in an EXTREAMLY RARE case, where ALL your values fall under the same key, will the hashmap map every item to the same key, and thus in a list implementation of collision handling, it would be O(N).

Hope that helps. You can read more about dictionaries/hashmap to understand better :)

aaha97 + 1 comment What I understand from your comment is that we are depending on the hardware (memory) provided to calculate the complexity of an algorithm. I think that is quite incorrect. Making assumptions like "virtually infinite memory" can lead to a lot of errors. And yes i agree about the "extremely rare" part and therefore accept that the average case complexity comes out to be Î©(1)

vijaychavda + 1 comment Uhh.. I never mentioned anything about hardware dependencies? Read again.

aaha97 + 1 comment Any hash function's efficiency is restricted by the memory available to implement it. The term "small data set" itself is relative to amount of memory available to you. The only way you can ensure that the collisions are "extremely rare" is by knowing your hardware supports that kind of memory. You might not have explicitly mentioned that thing, but that's what it boils down to.

peanut_lover_123 + 1 comment I recommend reading up on Universal Hash families. might answer some of your questions. Definitely anything higher than a G should be plenty to handle all the testcases. You might be able to prove that after reading on universal hash families.

aaha97 + 0 comments A very nice read indeed. I went through a few more lectures to make myself clear on this topic, especially because I seem to have received a lot of downvotes on my comment.

https://wiki.python.org/moin/TimeComplexity

So to clear my side of the argument, I would like you to go through the above link where they mention the average case being O(1) and (amortized) worst case for dictionary access being O(n).

https://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1

Also, the accepted answer in the above link mentions the exact reasons for this worst case i.e. failing assumptions.

bhaskar123u + 1 comment [deleted]bhaskar123u + 0 comments [deleted]

geekidharsh + 1 comment hi, i am trying really hard but I can't wrap my head around this:

dictPairs[i] = dictPairs.get(i, 0) + dict[i*r]

Can you please explain how you are able to determine the final count of triplets using this? thanks

marti733 + 1 comment From what I understand, the dictPairs are the pairs of values higher than the current index you're looking at. So dictPairs.get(i, 0) is looking to see if a pair already exists if not it's setting the frequency to 0. dict[ir] is getting the frequency of the higher of the pair and adding it to the frequency of the current pair. So if the current i is the first time you've encountered the number and the i times r has been seen you want to se the number of pairs to the current number of pairs added to the frequency of the higher number in the pair. Let's say you've seen 2 twice, 4 once, and haven't seen 1 then the number of pairs should be 2. (2(1), 4(1)) and (2(2), 4(1)). Meaning that when you see 1 the first time you'd want to increment the count which is done in (if i*r in dictPairs) you'd also add 1 to the dictPairs with 1 as the key so that would be 2 (the number of times you've seen 2) with the pairs (1(1), 2(1)) and (1(1), 2(2)). And so the next time you see 1, you'd increment the count again and the dictPairs[1] would increment by 2 so the total would be 4 with the pairs represented being (1(1), 2(1)), (1(1), 2(2)), (1(2), 2(1)), and (1(2), 2(2)).

geekidharsh + 0 comments Thanks so much. This really helped

ericsmitti + 0 comments incredible, great solution

budzinsa + 3 comments Nice... with Counter looks almost magic:

from collections import Counter def countTriplets(arr, r): result = 0 dictOne = Counter() dictPairs = Counter() for i in reversed(arr): result += dictPairs[i*r] dictPairs[i] += dictOne[i*r] dictOne[i] += 1 return result

edrouwendaal + 1 comment nice solution, for example in C# there is no such thing as a specialized counter dictionary, in this case it is very useful (I think)

budzinsa + 1 comment The most important advantage is lack of if else's which can easily be forgotten in corner cases. Without good test coverage almost undetected till that very rare bug appears in prodðŸ˜‰

edrouwendaal + 0 comments yes very nice also it improves readability

c_m_s_gan + 0 comments Alternative without using the collections module:

def countTriplets(arr, r): a = 0 cpairs = dict() cnumber = dict() for i in reversed(arr): # keys of cpairs = values in arr, corresponding values of cpairs = number of possible pairs with the number <key's number> whereby the 2nd element of each pair = <key's number>*r, and s.t. the keys occur after i in the list arr. # values of cnumber = the number of times that <key's number> has been encountered so far when looking at arr in reverse. if i*r in cpairs: a += cpairs[i*r] if not(i in cnumber): cnumber[i] = 0 if i*r in cnumber: if i in cpairs: cpairs[i] += cnumber[i*r] else: cpairs[i] = cnumber[i*r] # Necessary to put this line right at the end of the loop to properly handle the edge case r==1 cnumber[i] += 1 return a

HAMZA_SHAKEEL + 1 comment can somebody explain me this code i am new to python

c_m_s_gan + 0 comments This is based on the idea that, as we move through the array from the last to the first element, we use a dictionary keep track of the 'running' number of times each number has occurred.

We use a second dictionary to keep track of the 'running' number of times each pair of the form (x,rx) has occurred, where x is a number in the array. If we encounter a number, say k, such that r*(k) = a number we encountered at least once before, then the number of additional pairs (k,rk)) that can be formed with that number increases by the number of times rk has been encountered before.

Finally, for each number y, we add to the count the number of pairs of the form (yr,yr^2) that have occurred so far, and return that count after scanning through the entire array from back to front.

We could reverse-engineer this idea to implement a version where we start scanning through the array from the front to back (i.e. the other way around).

If there is anything code-wise that you don't understand, please specify the exact parts that require clarification.

lukezawada + 1 comment I'm not 100% I understand everything that is going on when r=1 versus my code which got stuck on it. But for what it's worth, I found my translation of the code above a bit easier to consume for non-Python speakers. Works just as well.

C# ver:

`long triplets = 0; Dictionary<long, long> dict = new Dictionary<long, long>(); Dictionary<long, long> dictPairs = new Dictionary<long, long>(); for(int index = arr.Count-1; index >= 0; index--) { if (dictPairs.ContainsKey(arr[index]*r)) triplets += dictPairs[arr[index]*r]; if (dict.ContainsKey(arr[index]*r)) { if(dictPairs.ContainsKey(arr[index])) dictPairs[arr[index]] = dictPairs[arr[index]] + dict[arr[index]*r]; else dictPairs[arr[index]] = dict[arr[index]*r]; } if(!dict.ContainsKey(arr[index])) dict.Add(arr[index], 1); else dict[arr[index]]++; } return triplets;`

pankajbelwal2012 + 0 comments Thanks

peanut_lover_123 + 0 comments @manndras I highly recommend that you read the editorial! You seem like the guy who would enjoy it. The left map/right map solution he mentions is O(n) (think there's a typo since the poster called it nlgn). Anyways, its actually even simpler than what you have (not to say that your explanations weren't helpful; they were!).

a141890 + 0 comments I did this.

def countTriplets(arr, r): buf = dict() count = 0 for v in reversed(arr): v2 = v*r buf.setdefault(v, [0, 0]) if v2 in buf: count += buf[v2][1] if v2 in buf: buf[v][1] += buf[v2][0] buf[v][0] += 1 # print(v, buf, count) return count

umairmaqsood48 + 0 comments C# version:

`static long countTriplets(List<long> arr, long r) { Dictionary<long, long> counts = new Dictionary<long, long>(); Dictionary<long, long> pairs = new Dictionary<long, long>(); long tripletCount = 0; for(long i=arr.Count-1; i>-1; i--) { long num = arr[(int)i]; long numR = num*r; if(pairs.ContainsKey(numR)) { tripletCount += pairs[numR]; } if(counts.ContainsKey(numR)) { if(pairs.ContainsKey(num)) pairs[num] += counts[numR]; else pairs[num] = counts[numR]; } if(counts.ContainsKey(num)) { counts[num]++; } else { counts[num] = 1; } } return tripletCount; }`

code_magic30 + 0 comments So, in this question we are assuming that the array would be in sorted order or it doesn't matter ?

nikhilgoyal104a1 + 13 comments This problem drove me crazy. Finally with the help of editorial and fellow hackerankers I was able to understand the solution. Also I felt this problem is slightly on the difficult side for beginners. The success perecentage of 42% and only around 5.5k submissions justifies it. Don't get disappointed if it doesen't click you. I had spend days trying to get my head over it. Here is the complete logic to help anyone :

Let's take an example to undertsand the core concept behind this problem : {1, 3, 3, 9, 3, 27, 81} . Let common ratio = 3.

1.We will consider every element to be our middle element during our iteration. For any such element a, the number of possible geometric pairs possible are, no. of a/r on the left of a x no. of axr on the right of a.

2.Lets take 9 as our element. 9/3 = 3. 9x3 = 27. The number of 3s present on left of 9 are 2. The number of 27s present on right of 9 is 1. Hence total no. of geometric pairs possible with 9 as the middle element is 2x1 = 2. Do this for all the elements and add them up to get the result.

3.We create an occurence map first and call it rightMap. Now for each element, we first decrement it's count by 1 from the rightMap. Now we check for the number of occurences of axr in the rightMap. ( Let me explain this step with a simple example , say the input is {1,1,1,1 } and ratio = 1, rightMap will be [1->4]. Now we need to check the number of times axr = 1 occurs on the right of a. We do this after decrementing the count of current value by 1 in the rightMap. So rightMap becomes [1->3] . 3 is the number of times aXr occurs on RHS of first 1 )

4.Now we check for a/r counts in left map. We multiply leftCount and rightCount and add them up for each element. The whole idea is that, for each element , leftMap contains the occurence map of the elements on the left of a and rightMap contains the occurence map of the elements on the right of a.

Here's my simple solution in java

static long countTriplets(List<Long> arr, long r) { Map<Long, Long> rightMap = getOccurenceMap(arr); Map<Long, Long> leftMap = new HashMap<>(); long numberOfGeometricPairs = 0; for (long val : arr) { long countLeft = 0; long countRight = 0; long lhs = 0; long rhs = val * r; if (val % r == 0) { lhs = val / r; } Long occurence = rightMap.get(val); rightMap.put(val, occurence - 1L); if (rightMap.containsKey(rhs)) { countRight = rightMap.get(rhs); } if (leftMap.containsKey(lhs)) { countLeft = leftMap.get(lhs); } numberOfGeometricPairs += countLeft * countRight; insertIntoMap(leftMap, val); } return numberOfGeometricPairs; } private static Map<Long, Long> getOccurenceMap(List<Long> test) { Map<Long, Long> occurenceMap = new HashMap<>(); for (long val : test) { insertIntoMap(occurenceMap, val); } return occurenceMap; } private static void insertIntoMap(Map<Long, Long> occurenceMap, Long val) { if (!occurenceMap.containsKey(val)) { occurenceMap.put(val, 1L); } else { Long occurence = occurenceMap.get(val); occurenceMap.put(val, occurence + 1L); } }

schut_julie + 1 comment

Sort 413 Discussions, By:

Please Login in order to post a comment