Find the three numbers from a list whose multiplication equals 180

To find three numbers from a list whose product is 180, the most efficient approach involves a combination of mathematical insight and algorithmic optimization.

Mechanics and Why

The brute-force solution uses three nested loops, checking every triplet, resulting in an O(N³) time complexity. This is highly inefficient for large lists.

A key optimization stems from the target number's factorization: 180 = 2² × 3² × 5. This means any three numbers multiplying to 180 must be composed solely of these prime factors. This allows for significant pre-filtering of the input list, a common data engineering pattern for reducing data volume before expensive computations.

The problem is a variant of the 3SUM problem. If we fix one number a from the list, we then need to find two other numbers b and c such that b * c = 180 / a. This subproblem can be solved efficiently:

* Hashing (O(N) space, O(N) average time for subproblem): Iterate through the remaining numbers. For each b, calculate target_val = 180 / b. Check if target_val exists in a hash set of previously seen numbers. This leads to an overall O(N²) average time complexity.
* Sorting + Two Pointers (O(1) space, O(N) for subproblem after sort): Sort the remaining numbers. Use two pointers, one starting from the beginning and one from the end, to find b and c that multiply to 180 / a. This approach yields an overall O(N² log N) or O(N²) complexity (if sorting is done once initially).

# Python: Optimized search for b*c = target_val
def find_two_product(nums, target_val):
    seen = set()
    for num in nums:
        if num == 0: continue # Handle zero appropriately
        if target_val % num == 0:
            complement = target_val // num
            if complement in seen:
                return True # Found b, c
            seen.add(num)
    return False

Trade-offs and Production Considerations

In a production data engineering context, the initial factorization and pre-filtering are paramount. For example, in a Spark job, you would filter a DataFrame to include only numbers that are factors of 180 (or whose prime factors are subsets of 180's prime factors) before applying the O(N²) algorithm. This significantly reduces the data processed by the more computationally intensive part. Hashing offers faster average-case lookups but consumes more memory (O(N) space) compared to the O(1) space of the two-pointer approach (after initial sorting).

In the interview, also mention handling edge cases like zeros (avoid division by zero), negative numbers (product could still be 180), and duplicates in the input list.