Product Pair

Time: O(n)

Space: O(n)

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?