## Sunday, April 23, 2017

### Find all pairs (a,b) and (c,d) in array which satisfy ab = cd - GeeksforGeeks

Find all pairs (a,b) and (c,d) in array which satisfy ab = cd - GeeksforGeeks
Given an array of distinct integers, the task is to find two pairs (a, b) and (c, d) such that ab = cd, where a, b, c and d are distinct elements.

Simple Solution is to run four loops to generate all possible quadruples of array element. For every quadruple (a, b, c, d), check if a*b = c*d. Time complexity of this solution is O(n4).
An Efficient Solution of this problem is to use hashing. We use product as key and pair as value in hash table.

```1. For i=0 to n-1
2.   For j=i+1 to n-1
a) Find  prod = arr[i]*arr[j]
b) If prod is not available in hash then make
H[prod] = make_pair(i, j) // H is hash table
c) If product is also available in hash
then print previous and current elements
of array
```
`void` `findPairs(``int` `arr[], ``int` `n)`
`{`
`    ``bool` `found = ``false``;`
`    ``unordered_map<``int``, pair < ``int``, ``int` `> > H;`
`    ``for` `(``int` `i=0; i<n; i++)`
`    ``{`
`        ``for` `(``int` `j=i+1; j<n; j++)`
`        ``{`
`            ``// If product of pair is not in hash table,`
`            ``// then store it`
`            ``int` `prod = arr[i]*arr[j];`
`            ``if` `(H.find(prod) == H.end())`
`                ``H[prod] = make_pair(i,j);`

`            ``// If product of pair is also available in`
`            ``// then print current and previous pair`
`            ``else`
`            ``{`
`                ``pair<``int``,``int``> pp = H[prod];`
`                ``cout << arr[pp.first] << ``" "` `<< arr[pp.second]`
`                     ``<< ``" and "` `<< arr[i]<<``" "``<<arr[j]<<endl;`
`                ``found = ``true``;`
`            ``}`
`        ``}`
`    ``}`
`    ``// If no pair find then print not found`
`    ``if` `(found == ``false``)`
`        ``cout << ``"No pairs Found"` `<< endl;`
`}`
Read full article from Find all pairs (a,b) and (c,d) in array which satisfy ab = cd - GeeksforGeeks