We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Count Triplets
  2. Discussions

Count Triplets

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 761 Discussions, By:

recency

Please Login in order to post a comment

  • joshgoddard
    3 months ago+ 0 comments

    O(N) c# solution that passes all test cases. Idea is, we iterate over each element. When we see an element, we keep a count of the number of tuples we have seen so far.

    static long countTriplets(List<long> arr, long r)
    {
        long count = 0;
        Dictionary<string, long> dic = new Dictionary<string, long>();
    
        long tmpCount;
        for (int i = 0; i < arr.Count; i++)
        {
            long num3 = arr[i];
    
            string key = "";
    
            if (num3 % r == 0)
            {
                long num2 = num3 / r;
                long num1 = num2 / r;
    
                if (i > 1)
                {
                    key = $"{num1}.{num2}";
                    if (dic.TryGetValue(key, out tmpCount))
                    {
                        count += tmpCount;
                    }
                }
    
                if (i > 0)
                {
                    if (dic.TryGetValue(num2.ToString(), out tmpCount))
                    {
                        key = $"{num2}.{num3}";
                        if (dic.TryGetValue(key, out long tmpCount2))
                        {
                            tmpCount2 += tmpCount;
    
                        }
                        else
                        {
                            tmpCount2 = tmpCount;
                        }
                        dic[key] = tmpCount2;
    
                    }
                }
            }
    
            key = num3.ToString();
            if (dic.TryGetValue(key, out tmpCount))
            {
                tmpCount++;
            }
            else
            {
                tmpCount = 1;
            }
            dic[key] = tmpCount;
    
        }
        return count;
    }
    
    0|
    Permalink
  • sbr_com
    3 months ago+ 0 comments

    my solution

    function countTriplets(arr, r) {
        let totalCount = 0
        const possibilities = {}
        const combos = {}
        
        arr.forEach((number) => {
          totalCount += (combos[number] || 0);
          const nextNumber = number * r;
          
          combos[nextNumber] = (combos[nextNumber] || 0) + (possibilities[number] || 0)
          possibilities[nextNumber] = (possibilities[nextNumber] || 0) + 1 
        })
    
        return totalCount
    }
    
    1|
    Permalink
  • neadam9
    3 months ago+ 0 comments

    Solution in python ...

    def countTriplets(arr, r):
        # Loop over the array and count valid triplets
        n_triplets = 0
        r2 = r*r
        d = {}
        d_r = {}
        d_rr = {}
        for i in range(len(arr)):
            if i > 1 and arr[i]%r2 == 0:
                # Total number of triples for this arr[i] = 
                # any triples found up to this point + all instances of doubles below this point 
                d_rr[arr[i]//r2] = d_rr.get(arr[i]//r2, 0) + d_r.get(arr[i]//r2, 0)
            if i > 0 and arr[i]%r == 0:
                # Total number of doubles for this arr[i] = 
                # any doubles found up to this point + all instances of arr[i] below this point 
                d_r[arr[i]//r] = d_r.get(arr[i]//r, 0) + d.get(arr[i]//r,0)
            d[arr[i]] = d.get(arr[i],0) + 1
    
        for k in d_rr:
            n_triplets += d_rr[k]
    
        return n_triplets
    
    0|
    Permalink
  • mtheofilos
    3 months ago+ 0 comments

    Based on the editorial notes in C++

    long countTriplets(vector<long> arr, long r) {
        unordered_map<long, long> left, right;
        
        long occurences = 0;
        
        for(auto const item : arr) {
            right[item]++;
        }
        
        for(auto const item : arr) {
            right[item]--;
            if (right.count(item * r) && (item % r == 0) && left.count(item / r)) {
                occurences += right[item * r] * left[item / r];
            }
            left[item]++;
        }
        
        return occurences;
    }
    
    0|
    Permalink
  • skepta
    4 months ago+ 0 comments

    I found this interesting fact. I implemented the same algorithm in C++ and PHP, turns out the PHP is the one passing the time limit.

    If you have trouble getting accepted with C++, I suggest you to use another language.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy