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()
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 = 8n = 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> |
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> |
The closest pair is 2 and 5
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
