Find a Pair with the Given Product

Title: Find a Pair with the Given Product

In this guide, you’ll learn how to find a pair of numbers in an array whose product equals a given target value. This is a classic array interview question that tests whether you can adapt the familiar hash-set lookup trick from the two-sum problem to multiplication instead of addition.

We’ll walk through a clean O(n) time approach using a HashSet, trace it by hand on a tricky input, and then cover the mistakes, edge cases, and follow-up questions an interviewer is likely to raise.

Understanding the Problem

Given an integer array nums and an integer targetProduct, the task is to find two elements in the array whose product equals targetProduct. If such a pair exists, report the two values; otherwise report that no pair was found.

Negative numbers and zero are both valid elements, and both require careful handling once the pair is built from a product rather than a sum. A value can only pair with itself if it genuinely appears twice in the array, not once.

Approach to Solve the Problem

1. Create an empty HashSet<Integer> named seen to record every number processed so far.
2. Iterate over the array nums one element at a time, calling the current value current.
3. If current is 0, check whether targetProduct is also 0 and whether seen already contains a zero; if so, a pair of zeros has been found.
4. Otherwise, when current is 0 and no pair is found yet, add 0 to seen and move on, since dividing by zero must never be attempted.
5. For a nonzero current, test whether targetProduct % current == 0 so the complement is a whole number rather than a fraction.
6. When it divides evenly, compute complement = targetProduct / current and check whether complement is already present in seen.
7. If complement is found, return the pair (complement, current) immediately, since no later element needs to be examined.
8. Otherwise add current to seen and continue scanning; if the loop finishes without a match, return an empty result.

Java Program to Find a Pair with the Given Product

import java.util.HashSet;
import java.util.Set;

public class FindPairWithGivenProduct {

    public static int[] findPairWithProduct(int[] nums, int targetProduct) {
        Set<Integer> seen = new HashSet<>();

        for (int current : nums) {
            if (current == 0) {
                if (targetProduct == 0 && seen.contains(0)) {
                    return new int[] {0, 0};
                }
                seen.add(0);
                continue;
            }

            if (targetProduct % current == 0) {
                int complement = targetProduct / current;
                if (seen.contains(complement)) {
                    return new int[] {complement, current};
                }
            }

            seen.add(current);
        }

        return new int[0];
    }

    public static void main(String[] args) {
        int[] nums = {10, 4, 8, 60, 20, 5};
        int targetProduct = 40;

        int[] result = findPairWithProduct(nums, targetProduct);

        if (result.length == 2) {
            System.out.println("Pair found: " + result[0] + " x " + result[1] + " = " + targetProduct);
        } else {
            System.out.println("No pair found with product " + targetProduct);
        }
    }
}

Explanation of the Program

The method findPairWithProduct scans nums once, using a HashSet<Integer> called seen to remember every value visited so far.

• current == 0 is handled first and separately, because dividing by zero would throw an ArithmeticException. A pair is only reported when a second zero shows up after the first.
• For any other value, targetProduct % current == 0 confirms the division produces a whole number before targetProduct / current is trusted as the complement.
• The complement is checked against seen before current itself is added to seen, which stops an element from being paired with itself unless it genuinely appears twice in the array.
• The method returns as soon as a match is found, so nums is never scanned further than necessary.

Step-by-Step Trace

Trace findPairWithProduct on nums = {7, 0, -3, 4, 0, -4} with targetProduct = -12. The method returns the pair (-3, 4) after four iterations.

At the end of each iteration, seen holds every element processed before the current one, so testing complement against seen can only ever match an element that appeared earlier in the array, which is exactly what keeps an index from pairing with itself.

Examples

Example 1: A Straightforward Pair

With nums = {10, 4, 8, 60, 20, 5} and targetProduct = 40, the method finds 10 and 4 as soon as 4 is reached, since 10 is already in seen.

int[] nums = {10, 4, 8, 60, 20, 5};
int targetProduct = 40;
int[] result = findPairWithProduct(nums, targetProduct);
// Output: Pair found: 10 x 4 = 40

Example 2: No Pair Exists

With nums = {1, 2, 3, 9, 8} and targetProduct = 100, no two elements multiply to 100, so the method scans the entire array and returns an empty result.

int[] nums = {1, 2, 3, 9, 8};
int targetProduct = 100;
int[] result = findPairWithProduct(nums, targetProduct);
// Output: No pair found with product 100

Example 3: A Pair of Zeros

With nums = {4, 7, 0, 0} and targetProduct = 0, the first 0 is only recorded in seen; the second 0 triggers the zero-pair check and the method returns (0, 0).

int[] nums = {4, 7, 0, 0};
int targetProduct = 0;
int[] result = findPairWithProduct(nums, targetProduct);
// Output: Pair found: 0 x 0 = 0

Common Mistakes to Avoid

These are the slip-ups that actually show up when candidates solve this problem, not generic advice.

• Computing targetProduct % current before checking for zero – dividing or taking the modulus of current == 0 throws an ArithmeticException. Always branch on zero first.
• Adding current to seen before checking its complement – this lets a single occurrence of a value satisfy itself, wrongly reporting a pair like (6, 6) when 6 appears only once. Check seen first, then add.
• Reporting a zero pair after seeing only one zero – returning as soon as the first 0 is read falsely claims a pair exists even when the array has a single zero. Require a second zero before returning.
• Trusting targetProduct / current without checking the remainder – integer division truncates, so complement can be wrong whenever current does not evenly divide targetProduct. Guard every division with targetProduct % current == 0.
• Printing nums[i] * nums[j] directly for verification – multiplying two large int values can silently overflow. Cast to long before multiplying if the inputs might be large.

Edge Cases to Test

Walk through these inputs before calling the solution finished.

• Empty array
• Single-element array
• No pair produces the target product
• Duplicate values that form the pair (e.g. target is a perfect square)
• Array containing exactly one zero with targetProduct equal to zero
• Array containing two or more zeros with targetProduct equal to zero
• Negative targetProduct with mixed-sign elements
• Integer.MIN_VALUE or Integer.MAX_VALUE present, where division or multiplication could overflow

Additional Considerations

The hash-set approach runs in O(n) time and uses O(n) extra space, since each element is visited once and at most all of them end up stored in seen.

If the array is already sorted, or mutation is allowed, a two-pointer sweep can solve the same problem in O(n log n) time (for the sort) but only O(1) extra space, trading memory for the sorting cost.

Division and modulus on int values never overflow the way multiplication can, so checking targetProduct % current is safe even for large inputs; only an explicit multiplication done for verification needs a long cast.

Interview Follow-up Questions

An interviewer rarely stops at the base case. Expect questions like these once the first solution works.

• What if you need every pair with the given product, not just the first one? – group values by frequency in a map first, then for each distinct value compute its complement and combine the counts, taking care not to double count a value paired with itself.
• What if the array is sorted and contains only non-negative numbers? – use two pointers starting at both ends, moving the left pointer right when the product is too small and the right pointer left when it is too large, for O(n) time and O(1) extra space.
• What if the input arrives as a stream of unknown length? – keep the same HashSet and check each new value against it as it arrives; termination comes from the end of the stream rather than the array length.
• What if you cannot use any extra memory beyond the input array? – sort the array in place and apply the two-pointer technique, accepting O(n log n) time in exchange for dropping the HashSet.
• What if no exact pair exists and you need the product closest to the target instead? – sort the array, sweep with two pointers, and track the smallest absolute difference between the running product and the target seen so far.

Conclusion

Finding a pair with a given product is a small twist on the classic hash-set lookup pattern, but zero and negative values force you to handle division carefully instead of reaching for it blindly. Once the zero case and the divisibility check are in place, the rest of the logic is a single clean pass over the array.

Try adapting findPairWithProduct to return every matching pair, or to work on a sorted array with two pointers, to make sure the idea has fully sunk in. You can learn more about array-based interview problems in the Arrays category on this site.