Find pair with greatest product in array - GeeksforGeeks

Find pair with greatest product in array - GeeksforGeeks
Given an array of n elements, the task is to find the greatest number such that it is product of two elements of given array. If no such element exists, print -1. Elements are within the range of 1 to 10^5.

1. Create an empty hash table and store all array elements in it.
2. Sort the array in ascending order.
3. Pick elements one by one from end of the array.
4. And check if there exists a pair whose product is equal to that number. In this efficiency can be achieved. The idea is to reach till sqrt of that number. If we don’t get the pair till sqrt that means no such pair exists. We use hash table to make sure that we can find other element of pair in O(1) time.
5. Repeat steps 2 to 3 until we get the element or whole array gets traversed.

int findGreatest(int arr[], int n)

{

    // Store occurrences of all elements in hash

    // array

    unordered_map<int, int> m;

    for (int i = 0 ; i < n; i++)

        m[arr[i]]++;

 

    // Sort the array and traverse all elements from

    // end.

    sort(arr, arr+n);

 

    for (int i=n-1; i>1; i--)

    {

        // For every element, check if there is another

        // element which divides it.

        for (int j=0; j<i && arr[j]<=sqrt(arr[i]); j++)

        {

            if (arr[i] % arr[j] == 0)

            {

                int result = arr[i]/arr[j];

 

                // Check if the result value exists in array

                // or not if yes the return arr[i]

                if (result != arr[j] && m[result] > 0)

                    return arr[i];

 

                // To handle the case like arr[i] = 4 and

                // arr[j] = 2

                else if (result == arr[j] && m[result] > 1)

                    return arr[i];

            }

        }

    }

    return -1;

}

Read full article from Find pair with greatest product in array - GeeksforGeeks