Question

Use pseudocode to describe an algorithm for the procedure: int[][] find_pairs( int array[], int value ). Given a sorted array of distinct integers and a single integer value, find all pairs of indexes in the list whose product is equal to the value. Return the index pairs on the same row of a two-dimensional array. Note, m will be the number of rows and total number of pairs found, while 2 will be the number of columns along every row [the first and second index position. Prove the time complexity of your solution. If you solve the problem in O(n) time, +3 Extra Credit Points.

Example Data
Array: [ 1, 2, 4, 5, 6, 9, 10, 15, 20 ]
Value: 20

Return: 0, 8
1, 6
2, 3

Answer 1

The code is written in c++ 14 with complexity O(n). This program also works for unsorted array.

If you still have any queries please comment. I will definitely clarify it.

EXPLANATION ( ALGORITHM )

Create an result matrix of 2 columns.

Create a hash table (set) to store the valid elements that have been encountered.

Traverse array elements and do following for every element arr[i].

1) if (n < 2 ) // single element array
   terminate the program.

2) If ( arr[i] == 0 && x == 0 )
   add index of all elements with index of arr[i] in the result matrix.
else
   ignore arr[i] (continue).

3) If ( x % arr[i] == 0 && x/arr[i] exists in table)
   add indexes of arr[i] and x/arr[i] in the result matrix.

Finally, display the result matrix.

PROGRAM

#include
#include
using namespace std;

int result[][2]={-1}; // stores the index of elements with product x
int k=0;           // number of rows in result matrix

// stores the indexes of pairs with given product x in result matrix
void product_pair(int arr[], int n, int x, int idx[])
{
   if (n < 2)
       return;

   // Create an empty set and insert first element into it
   set s;

   for (int i=0; i    {
       // 0 case must be handles explicitly as x % 0 is undefined
       if (arr[i] == 0)
       {
           if (x == 0)
           {
               for(int j=0;j                {
                   if(i!=j)
                   {
                       result[k][0] = idx[ arr[j] ];
                       result[k][1] = idx[ arr[i] ];
                       k++;
                   }
               }
           }

           else
               continue;
       }

       // x / arr[i] exists in hash, then we found a pair
       if ((x % arr[i]) == 0)
       {
           if (s.find(x/arr[i]) != s.end())
           {
               result[k][0] = idx[ x/arr[i] ];
               result[k][1] = idx[ arr[i] ];
               k++;
           }

           // Insert arr[i]
           s.insert(arr[i]);
       }
   }
}

int main()
{
   int arr[] = { 1, 2, 4, 5, 6, 9, 10, 15, 20};    // array initialization
   int x = 20;    // required product
  
   int n = sizeof(arr)/sizeof(arr[0]);
  
   int idx[100000]; // for storing the index of array elements
   for(int i=0;i<100000;i++)
       idx[i] = -1;
  
   for(int i=0;i        idx[arr[i]] = i;  
  
   product_pair(arr, n, x, idx);
  
   // result matrix
   for(int i=0;i        cout<       
   return 0;
}

IMAGE OF CODE

IMAGE OF OUTPUT