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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Triple sum
  2. Discussions

Triple sum

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 211 Discussions, By:

recency

Please Login in order to post a comment

  • nleo575
    3 weeks ago+ 0 comments

    Python3 soltuion. Time: O(nlogn). Similar to the previous comment but I implimted by own binary search algorithm and included an optimization to reduce searching once q is greater than all elements in p and r.

    def triplets(a, b, c):
        # Use binary search to find where q is, or should be in the array
        def binary_search(arr, target):
            high, low = len(arr) - 1, 0
            mid = (high + low) // 2
            sample = arr[mid]
            l_arr = len(arr)
            while low <= high:
                if target < sample:
                    high = mid - 1
                elif target > sample:
                    low = mid + 1
                else:
                    # Add 1 since we want count of elements q is >=
                    return mid + 1
                
                mid = (high + low ) // 2
                sample = arr[mid]
            
            # Add 1 since we want count of elements q is >=
            return high + 1  # Will be 0 or len(arr)
        
        a, b, c = list(set(a)), list(set(b)), list(set(c))
        a.sort()
        b.sort()
        c.sort()
    
        a_len, c_len = len(a), len(c)
        max_pr = product = result = 0
        for q in b:
            if max_pr:
                result += max_pr
            else:   
                p = binary_search(a, q)
                r = binary_search(c, q)
                if p and r:
                    product = p * r
                    if p == a_len and r == c_len:
                        # Once q is > all elements in p and r, simply resuse
                        # this max product.
                        max_pr = product
    
                    result += product
        
        return result
    
    0|
    Permalink
  • ksathursan1408
    2 months ago+ 0 comments

    O(nlogn) Solution

    import bisect
    def triplets(a, b, c):
        count = 0
        a = list(set(a))
        b = list(set(b))
        c = list(set(c))
        a.sort()
        b.sort()
        c.sort()
        for element in b:
            c1 = bisect.bisect(a,element)
            c2 = bisect.bisect(c,element)
            count += c1*c2
        return count
    
    0|
    Permalink
  • maurits_moeys
    4 months ago+ 1 comment

    Issues with test case 4? lena might just be int32, but lena+1 requires int64. (or lenb, lenc).

    1|
    Permalink
  • evananindya
    5 months ago+ 1 comment

    I am using Go, and the best I can do is iterating over sorted a, b, and c. My code succeeded in 9/10 of test cases and timed out in test case 4. Is this problem attainable with Go at all? I think to solve the problem in time, sorted set or tree map is needed. But Go supports neither.

    0|
    Permalink
  • yoursungjin_us
    5 months ago+ 0 comments

    why would you call it triple 'sum' when there's no summation involved?

    2|
    Permalink
Load more conversations

Need Help?


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