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.
- Triple sum
- Discussions
Triple sum
Triple sum
+ 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 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
+ 1 comment Issues with test case 4?
lena
might just beint32
, butlena+1
requiresint64
. (orlenb
,lenc
).
+ 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 comments why would you call it triple 'sum' when there's no summation involved?
Load more conversations
Sort 211 Discussions, By:
Please Login in order to post a comment