Product Pair

Time: O(n)

Space: O(n)

Problem Overview

We need to find two numbers in the array whose product equals the target.

Intuition

We need to find two numbers in the array whose product equals the target. A single-pass hash-set approach works: as we iterate, we ask "have I seen the complement of target/current?" If yes, we have a pair. The hash-set prevents revisiting the same number.

Algorithm

1Create an empty hash-set to track viewed numbers.
2For each number in the array:
3 If the number is 0: check if target is also 0 (0 * anything = 0). If yes, return true.
4 Otherwise: if target is divisible by this number, compute complement = target / number.
5 If the complement is in the set, we found a pair, return true.
6 Add the current number to the set for future lookups.
7If loop completes without finding a pair, return false.

Example Walkthrough

Input: arr = [2, 4, 6, 3], target = 12

1. num=2: target%2==0, complement=6. Viewed={}, add 2.
2. num=4: target%4==0, complement=3. Viewed={2}, add 4.
3. num=6: target%6==0, complement=2. Viewed={2,4}, 2 is in set ? found pair (6,2).
4. Return true.

Output: true

Common Pitfalls

• Zero is a special case: 0 * x = 0 for any x, so the check target==0 must happen separately.
• Integer division: target/num is exact only if target%num==0; always check divisibility first.
• One-pass order matters: we check before adding to set, so a number does not pair with itself unless it appears twice and target is a perfect square.

Product Pair.java

Java


import java.util.*;

// Approach: Hash-set single pass. For each number, check if target/number already exists in set.
// Handle zero separately. If both number and complement exist, we found a pair.
// Time: O(n) Space: O(n)

class Solution {

    public boolean isProduct(int[] arr, long target) {
        Set<Long> viewed = new HashSet<>();

        for (int num : arr) {
            if (num == 0) {
                if (target == 0) {
                    return true;
                }
            } else if (target % num == 0) {
                long needed = target / num;
                if (viewed.contains(needed)) {
                    return true;
                }
                viewed.add((long) num);
            }
        }
        
        return false;
    }
}

Was this solution helpful?