Count Triplets

Sort by

recency

|

814 Discussions

|

  • + 0 comments

    This one was a doozy! Took me way longer then I'd care to admit. JS solution (forgive my nesting 😅):

    function countTriplets(arr, r) {
        let result = 0;
        
        const values = {};
        const pairs = {};
        
        for(const v of arr) {
          const prev = v/r;
          
          if(prev in values) {
            if (prev in pairs) result += pairs[prev];
            
            pairs[v] = (pairs[v] ?? 0) + values[prev];
          }
          
          values[v] = (values[v] ?? 0) + 1;
        }
        
        return result;
    }
    
  • + 0 comments

    Why is this failing hidden test case 6 :(

    I came up with idea of moving forward and keeping a track of singles and doubles that have happened. This is passing all test cases except test case 6 :(

    static long countTriplets(List<long> arr, long r)
    {
        Dictionary<long, long> singles = new();
        Dictionary<long, long> doubles = new();
        long count = 0;
    
        foreach (var num in arr)
        {
            long keyByr = num / r;
    
            // If num completes a triplet
            if (doubles.ContainsKey(keyByr))
            {
                count += doubles[keyByr];
            }
    
            // If num can be a middle of triplet
            if (singles.ContainsKey(keyByr))
            {
                if (doubles.ContainsKey(num))
                    doubles[num] += singles[keyByr];
                else
                    doubles[num] = singles[keyByr];
            }
    
            // Count num as potential start
            if (singles.ContainsKey(num))
                singles[num]++;
            else
                singles[num] = 1;
        }
    
        return count;
    }
    
  • + 1 comment

    can someone please help me understand the problem with my code??

    def countTriplets(arr, r):
        d = defaultdict(int)
        count = 0
        for i in arr:
            d[i] += 1
        for i in d:
            if i == i*r and i == i*r*r:
                count = count + (d[i] * (d[i]-1) * (d[i] - 2)) // 6
            else:
                if i*r in d and i*r*r in d:
                    count = count + d[i] * d[i*r] * d[i*r*r]
            
        return count
    
  • + 0 comments

    Recursive solution:

    def countTriplets(arr, r):
        sys.setrecursionlimit(10**6) #Avoid recursion error
        def rec_function(index, seconds, thirds, count):
            if index >= len(arr):
                return count
            i = arr[index]
            if i in thirds:
                count += thirds[i]
            if i in seconds:
                thirds[i * r] = thirds.get(i * r, 0) + seconds[i]
            seconds[i * r] = seconds.get(i * r, 0) + 1
            return rec_function(index + 1, seconds, thirds, count)
        
        return rec_function(0, {}, {}, 0)
    
  • + 1 comment
    def countTriplets(arr, r):
        seconds = {}
        thirds = {}
        count = 0
    
        for i in arr:
            
            if i in thirds:
                count += thirds[i]
    
            if i in seconds:
                if i * r in thirds:
                    thirds[i * r] += seconds[i]
                else:
                    thirds[i * r] = seconds[i]
    
            if i * r in seconds:
                seconds[i * r] += 1
            else:
                seconds[i * r] = 1
    
        return count