Problem statement

https://binarysearch.com/problems/Three-Doubled-Numbers/

Solution

The idea is for each index i find how many elements with A[i]//2 we have to the left and how many elements with A[i]*2 we have to the right.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        n = len(A)
        d_lft, lft = Counter(), [0]*n
        d_rgh, rgh = Counter(), [0]*n

        for i in range(n):
            if A[i] % 2 == 0: lft[i] = d_lft[A[i]//2]
            d_lft[A[i]] += 1

        for i in range(n-1, -1, -1):
            rgh[i] = d_rgh[A[i]*2]
            d_rgh[A[i]] += 1

        return sum(x*y for x, y in zip(lft, rgh))