Closest product pair in an array

0 0 9 minutes read

Given an array of non-negative integers and a number x, find a pair in the array whose product is closest to x.

Examples:

Input : arr[] = [2, 3, 5, 9]
        x = 47
Output : {5, 9}

Input : arr[] = [2, 3, 5, 9]
        x = 8
Output : {2, 5}

Method 1
A simple solution is to consider every pair and keep track of the closest pair (absolute difference between pair product and x is minimum). Finally, print the closest pair. The time complexity of this solution is O( $n^2$ )

Implementation:-

C++

// Simple C++ program to find the pair with 
// product closest to a given no. 
#include <bits/stdc++.h> 
using namespace std; 
  
// Prints the pair with product closest to x 
void printClosest(int arr[], int n, int x) 
{ 
    // pair to store answer pair 
    pair<int, int> ans; 
  
    // temp to store the minimum current difference 
    int temp = INT_MAX; 
  
    // iterating over array 
    for (int i = 0; i < n - 1; i++) { 
        for (int j = i + 1; j < n; j++) { 
            // checking for minimum difference 
            if (abs(arr[i] * arr[j] - x) <= temp) { 
                ans.first = arr[i]; 
                ans.second = arr[j]; 
                temp = abs(arr[i] * arr[j] - x); 
            } 
        } 
    } 
    cout << ans.first << " " << ans.second; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = { 2, 3, 5, 9 }, x = 8; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printClosest(arr, n, x); 
    return 0; 
} 
// This code is contributed by shubhamrajput6156

Java

// Java program to find the pair with product closest to a 
// given number  
  
public class Main { 
  
    // Prints the pair with product closest to x 
    public static void printClosest(int[] arr, int n, int x) 
    { 
        int closestFirst = 0, closestSecond = 0; 
        int temp = Integer.MAX_VALUE; 
  
        // iterating over array 
        for (int i = 0; i < n - 1; i++) { 
            for (int j = i + 1; j < n; j++) { 
                // checking for minimum difference 
                if (Math.abs(arr[i] * arr[j] - x) <= temp) { 
                    closestFirst = arr[i]; 
                    closestSecond = arr[j]; 
                    temp = Math.abs(arr[i] * arr[j] - x); 
                } 
            } 
        } 
        System.out.println(closestFirst + " "
                           + closestSecond); 
    } 
  
    // Driver program 
    public static void main(String[] args) 
    { 
        int[] arr = { 2, 3, 5, 9 }; 
        int x = 8; 
        int n = arr.length; 
        printClosest(arr, n, x); 
    } 
}

Python3

# Simple Python3 program to find 
# the pair with product closest 
# to a given no. 
  
# Prints the pair with product closest to x 
def printClosest(arr: list, n: int, x: int): 
  
    # To store indexes 
    # of result pair 
    ans_a, ans_b = 0, 0
      
    # temp to store the minimum current difference 
    temp = float("inf") 
  
    for i in range(n - 1): 
        for j in range(i + 1, n): 
            
            # checking for minimum difference 
            if abs(arr[i] * arr[j] - x) <= temp: 
                ans_a, ans_b = arr[i], arr[j] 
                temp = abs(arr[i] * arr[j] - x) 
    print(ans_a, ans_b) 
  
# driver code 
arr = [2, 3, 5, 9] 
x = 8
n = len(arr) 
printClosest(arr, n, x) 
  
# This code is contributed by redmoonz.

C#

using System; 
  
namespace ClosestPair 
{ 
    class Program 
    { 
        // Function to find the pair with product closest to x 
        static void PrintClosest(int[] arr, int n, int x) 
        { 
            int closestFirst = 0, closestSecond = 0; 
            int temp = int.MaxValue; 
  
            // iterating over array 
            for (int i = 0; i < n - 1; i++) 
            { 
                for (int j = i + 1; j < n; j++) 
                { 
                    // checking for minimum difference 
                    if (Math.Abs(arr[i] * arr[j] - x) <= temp) 
                    { 
                        closestFirst = arr[i]; 
                        closestSecond = arr[j]; 
                        temp = Math.Abs(arr[i] * arr[j] - x); 
                    } 
                } 
            } 
            Console.WriteLine(closestFirst + " " + closestSecond); 
        } 
  
        static void Main(string[] args) 
        { 
            int[] arr = { 2, 3, 5, 9 }; 
            int x = 8; 
            int n = arr.Length; 
            PrintClosest(arr, n, x); 
        } 
    } 
} 

Javascript

<script> 
  
// javascript program to find the pair with 
// product closest to a given no. 
  
// Prints the pair with product closest to x 
function printClosest(arr, n, x){ 
  
    // temp to store the minimum current difference 
    var temp = 1e9; 
    var a, b; 
    // iterating over array 
    for (let i = 0; i < n - 1; i++) { 
        for (let j = i + 1; j < n; j++) { 
            // checking for minimum difference 
            if (Math.abs(arr[i] * arr[j] - x) <= temp) { 
                a= arr[i]; 
                b=arr[j]; 
                temp = Math.abs(arr[i] * arr[j] - x); 
            } 
        } 
    } 
    console.log(a , b); 
      
} 
  
    const arr=[2, 3, 5, 9]; 
    const n = arr.length; 
    const x =8; 
      
    printClosest(arr, n, x); 
      
    //this code is contributed by bhardwajji 
<script>

Output

2 5

Time Complexity:- O(N^2)

Auxiliary Space:- O(1)

Method 2: O(n Log n)

Sort the array
Initialize a variable diff as infinite (Diff is used to store the difference between a pair and x). We need to find the minimum diff.
Traverse the array and for each i, do the following :
- Find the lower bound for x/arr[i] in the sub-array on the right of arr[i], i.e., in subarray arr[i+1..n-1]. Let it be denoted by l.
- Find the upper bound for x/arr[i] in the sub array on the right of arr[i], i.e., in sub array arr[i+1..n-1]. Let it be denoted by u.
- If min(abs((arr[i] * l) – x), abs((arr[i] * u) – x)) < diff, then update diff and result

Method 3 O(n for sorted)
An efficient solution can find the pair in O(n) time. The following is the detailed algorithm.

1) Initialize a variable diff as infinite 
   (Diff is used to store the difference 
   between pair and x).  We need to find 
   the minimum diff.
2) Initialize two index variables l and r
   in the given sorted array.
   (a) Initialize first to the leftmost index:  
        l = 0
   (b) Initialize second  the rightmost index: 
        r = n-1
3) Loop while l < r.
   (a) If  abs((arr[l] * arr[r]) - x) < diff  
       then update diff and result 
   (b) Else if((arr[l] * arr[r]) <  x)  then
       l++
   (c) Else r--

The following is the implementation of the above algorithm.

C++

// Simple C++ program to find the pair with 
// product closest to a given no. 
#include <bits/stdc++.h> 
using namespace std; 
  
// Prints the pair with product closest to x 
void printClosest(int arr[], int n, int x) 
{ 
    int res_l, res_r; // To store indexes of result pair 
  
    // Initialize left and right indexes and  
    // difference between pair product and x 
    int l = 0, r = n - 1, diff = INT_MAX; 
  
    // While there are elements between l and r 
    while (r > l) { 
  
        // Check if this pair is closer than  
        // the closest pair so far 
        if (abs(arr[l] * arr[r] - x) < diff) { 
            res_l = l; 
            res_r = r; 
            diff = abs(arr[l] * arr[r] - x); 
        } 
  
        // If this pair has more product,  
        // move to smaller values. 
        if (arr[l] * arr[r] > x) 
            r--; 
  
        else // Move to larger values 
            l++; 
    } 
  
    cout << " The closest pair is "
        << arr[res_l] << " and " << arr[res_r]; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    int arr[] = { 2, 3, 5, 9 }, x = 8; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printClosest(arr, n, x); 
    return 0; 
} 

Java

// Simple Java program to find  
// the pair with product closest  
// to a given no. 
import java.io.*; 
  
class GFG 
{ 
// Prints the pair with  
// product closest to x 
static void printClosest(int arr[],  
                         int n, int x) 
{ 
    // To store indexes of result pair 
    int res_l = 0, res_r = 0;  
  
    // Initialize left and right  
    // indexes and difference  
    // between pair product and x 
    int l = 0, r = n - 1, diff = Integer.MAX_VALUE; 
  
    // While there are  
    // elements between l and r 
    while (r > l)  
    { 
  
        // Check if this pair is closer   
        // than the closest pair so far 
        if (Math.abs(arr[l] * arr[r] - x) < diff) 
        { 
            res_l = l; 
            res_r = r; 
            diff = Math.abs(arr[l] * arr[r] - x); 
        } 
  
        // If this pair has more product,  
        // move to smaller values. 
        if (arr[l] * arr[r] > x) 
            r--; 
  
        // Move to larger values 
        else 
            l++; 
    } 
  
    System.out.print("The closest pair is "); 
    System.out.print (arr[res_l] +  
                         " and " +  
                      arr[res_r]); 
} 
  
// Driver Code 
public static void main (String[] args)  
{ 
int arr[] = {2, 3, 5, 9}; 
int x = 8; 
int n = arr.length; 
printClosest(arr, n, x); 
} 
} 
  
// This code is contributed by anuj_67. 

Python3

# Simple Python3 program to find  
# the pair with product closest 
# to a given no. 
import sys 
  
# Prints the pair with 
# product closest to x 
def printClosest(arr, n, x): 
      
    # To store indexes  
    # of result pair 
    res_l = 0;  
    res_r = 0;  
  
    # Initialize left and right  
    # indexes and difference  
    # between pair product and x 
    l = 0;  
    r = n - 1;  
    diff = sys.maxsize; 
  
    # While there are elements 
    # between l and r 
    while (r > l): 
  
        # Check if this pair is  
        # closer than the closest  
        # pair so far 
        if (abs(arr[l] * 
                arr[r] - x) < diff):  
            res_l = l; 
            res_r = r; 
            diff = abs(arr[l] * 
                       arr[r] - x); 
  
        # If this pair has more  
        # product, move to smaller 
        # values. 
        if (arr[l] * arr[r] > x): 
            r = r - 1; 
  
        # Move to larger values 
        else: 
            l = l + 1; 
  
    print("The closest pair is", arr[res_l] , 
                          "and", arr[res_r]); 
  
# Driver Code 
arr = [2, 3, 5, 9];  
x = 8; 
n = len(arr); 
printClosest(arr, n, x); 
  
# This code is contributed 
# by rahul 

C#

// Simple C# program to find  
// the pair with product closest  
// to a given no. 
using System; 
  
class GFG 
{ 
// Prints the pair with  
// product closest to x 
static void printClosest(int []arr,  
                         int n, int x) 
{ 
    // To store indexes of result pair 
    int res_l = 0, res_r = 0;  
  
    // Initialize left and right  
    // indexes and difference  
    // between pair product and x 
    int l = 0, r = n - 1,  
        diff = int.MaxValue; 
  
    // While there are  
    // elements between l and r 
    while (r > l)  
    { 
  
        // Check if this pair is closer  
        // than the closest pair so far 
        if (Math.Abs(arr[l] *  
                     arr[r] - x) < diff) 
        { 
            res_l = l; 
            res_r = r; 
            diff = Math.Abs(arr[l] *  
                            arr[r] - x); 
        } 
  
        // If this pair has more product,  
        // move to smaller values. 
        if (arr[l] * arr[r] > x) 
            r--; 
  
        // Move to larger values 
        else
            l++; 
    } 
  
    Console.Write("The closest pair is "); 
    Console.Write (arr[res_l] +  
                      " and " +  
                   arr[res_r]); 
} 
  
// Driver Code 
public static void Main ()  
{ 
int []arr = {2, 3, 5, 9}; 
int x = 8; 
int n = arr.Length; 
printClosest(arr, n, x); 
} 
} 
  
// This code is contributed by anuj_67. 

PHP

<?php 
// Simple PHP program to find  
// the pair with product closest 
// to a given no. 
  
// Prints the pair with 
// product closest to x 
function printClosest($arr, $n, $x) 
{ 
    // To store indexes  
    // of result pair 
    $res_l; $res_r;  
  
    // Initialize left and right  
    // indexes and difference  
    // between pair product and x 
    $l = 0; $r = $n - 1; $diff = PHP_INT_MAX; 
  
    // While there are elements 
    // between l and r 
    while ($r > $l) 
    { 
  
        // Check if this pair is  
        // closer than the closest  
        // pair so far 
        if (abs($arr[$l] *  
                $arr[$r] - $x) < $diff)  
        { 
            $res_l = $l; 
            $res_r = $r; 
            $diff = abs($arr[$l] *  
                        $arr[$r] - $x); 
        } 
  
        // If this pair has more   
        // product, move to smaller 
        // values. 
        if ($arr[$l] * $arr[$r] > $x) 
            $r--; 
  
        // Move to larger values 
        else 
            $l++; 
    } 
  
    echo " The closest pair is " ,  
          $arr[$res_l] , " and " ,  
                     $arr[$res_r]; 
} 
  
// Driver Code 
$arr = array(2, 3, 5, 9);  
$x = 8; 
$n = count($arr); 
printClosest($arr, $n, $x); 
  
// This code is contributed by anuj_67. 
?> 

Javascript

<script> 
  
// Simple Javascript program to find the pair with 
// product closest to a given no. 
  
// Prints the pair with product closest to x 
function printClosest(arr, n, x) 
{ 
    var res_l, res_r; // To store indexes of result pair 
  
    // Initialize left and right indexes and  
    // difference between pair product and x 
    var l = 0, r = n - 1, diff = 10000000000; 
  
    // While there are elements between l and r 
    while (r > l) { 
  
        // Check if this pair is closer than  
        // the closest pair so far 
        if (Math.abs(arr[l] * arr[r] - x) < diff) { 
            res_l = l; 
            res_r = r; 
            diff = Math.abs(arr[l] * arr[r] - x); 
        } 
  
        // If this pair has more product,  
        // move to smaller values. 
        if (arr[l] * arr[r] > x) 
            r--; 
  
        else // Move to larger values 
            l++; 
    } 
  
    document.write( " The closest pair is "
        + arr[res_l]  + " and " + arr[res_r]); 
} 
  
// Driver program to test above functions 
var arr = [2, 3, 5, 9 ], x = 8; 
var n = arr.length; 
printClosest(arr, n, x); 
  
  
</script>

Output

 The closest pair is 2 and 5

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!