How to find all pairs (a,b) and (c,d) in an array which satisfy ab = cd with O(n²) time complexity using a hashmap data type

Question

Given a list of integers, how can all pairs (ie. a x b = c x d; such that a != b != c != e) be found under minimal time complexity?

I've tried using a hashmap data type, which basically does the product calculation, checks whether it's already found within a hashmap, and if it is it attributes the value of the increment counter of the nested for loops with the Pair object type found within the hashmap.

Pair is an object storing the index of the first and second numbers in a pair. The hashmap stores the product as the key and the pair as the value.

The problem with my code is that when it comes to the following scenario...

a x b = c x d = e x f

...it doesn't work due to the fact it only makes the following links...

a x b = c x d and a x b = e x f

...and is unable to reach:

c x d = e x f

For example the following array produces incorrect results:

int[] A = {1,2,3,4,6,12};

I expect the sole problem is because a hashmap only takes one value for a given key. I've tried to maybe change the hashmap declaration to an array of pairs but quickly realised I would be needing to add another for loop, and thus increasing the time complexity.

Any ideas what I can do to maintain the O(n²) and provide correct results?

Answer 1

My take at it:

Store a Set of Pairs for each product. This should take care of duplicates. You need to consider Pairs equal if they consist of the same numbers.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;

public class Main {

  static int[] data = {1,2,3,4,6,12};

  static class Pair {

    public Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }

    public int x;
    public int y;

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      Pair pair = (Pair) o;
      return
        x == pair.x && y == pair.y ||
        x == pair.y && y == pair.x;
    }

    @Override
    public int hashCode() {
      return Objects.hash(x * y);
    }
  }

  public static void main(String[] args){

    HashMap<Integer, HashSet<Pair>> products = new HashMap<>();

    // index all pairs by product in o^2 loop
    for (int i=0;i<data.length;i++){
      for (int j=i+1;j<data.length;j++){
        int a = data[i];
        int b = data[j];
        Integer p = a*b;
        if (!products.containsKey(p)){
          products.put(p, new HashSet<>());
        }
        HashSet<Pair> knownPairs = products.get(p);
        Pair pair = new Pair(a, b);
        knownPairs.add(pair);
      }
    }

    // output results
    for (Integer product: products.keySet()) {
      System.out.print("product: "+product+" -");
      HashSet<Pair> pairs = products.get(product);
      for (Pair pair : pairs) {
        System.out.print(" "+pair.x+"x"+pair.y);
      }
      System.out.println();
    }


  }

}