Given two sorted arrays A[] and B[] consisting of N and M integers respectively, the task is to find the Kth smallest number in the array formed by the product of all possible pairs from array A[] and B[] respectively.
Examples:
Input: A[] = {1, 2, 3}, B[] = {-1, 1}, K = 4
Output: 1
Explanation: The array formed by the product of any two numbers from array A[] and B[] respectively is prod[] = {-3, -2, -1, 1, 2, 3}. Hence, the 4th smallest integer in the prod[] array is 1.Input: A[] = {-4, -2, 0, 3}, B[] = {1, 10}, K = 7
Output: 3
Approach: The given problem can be solved with the help of Binary Search over all possible values of products. The approach discussed here is very similar to the approach discussed in this article. Below are the steps to follow:
- Create a function check(key), which returns whether the number of elements smaller than the key in the product array is more than K or not. It can be done using the two-pointer technique similar to the algorithm discussed in the article here.
- Perform a binary search over the range [INT_MIN, INT_MAX] to find the smallest number ans such that the number of elements smaller than ans in the product array is at least K.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define int long long// Function to check if count of elements// greater than req in product array are// more than K or notbool check(int req, vector<int> posA, vector<int> posB, vector<int> negA, vector<int> negB, int K){ // Stores the count of numbers less // than or equal to req int cnt = 0; // Case with both elements of A[] and // B[] are negative int first = 0; int second = negB.size() - 1; // Count number of pairs formed from // array A[] and B[] with both elements // negative and there product <= req while (first < negA.size()) { while (second >= 0 && negA[first] * negB[second] <= req) second--; // Update cnt cnt += negB.size() - second - 1; first++; } // Case with both elements of A[] and // B[] are positive first = 0; second = posB.size() - 1; // Count number of pairs formed from // array A[] and B[] with both elements // positive and there product <= req while (first < posA.size()) { while (second >= 0 && posA[first] * posB[second] > req) second--; // Update cnt cnt += second + 1; first++; } // Case with elements of A[] and B[] // as positive and negative respectively first = posA.size() - 1; second = negB.size() - 1; // Count number of pairs formed from // +ve integers of A[] and -ve integer // of array B[] product <= req while (second >= 0) { while (first >= 0 && posA[first] * negB[second] <= req) first--; // Update cnt cnt += posA.size() - first - 1; second--; } // Case with elements of A[] and B[] // as negative and positive respectively first = negA.size() - 1; second = posB.size() - 1; // Count number of pairs formed from // -ve and +ve integers from A[] and // B[] with product <= req for (; first >= 0; first--) { while (second >= 0 && negA[first] * posB[second] <= req) second--; // Update cnt cnt += posB.size() - second - 1; } // Return Answer return (cnt >= K);}// Function to find the Kth smallest// number in array formed by product of// any two elements from A[] and B[]int kthSmallestProduct(vector<int>& A, vector<int>& B, int K){ vector<int> posA, negA, posB, negB; // Loop to iterate array A[] for (const auto& it : A) { if (it >= 0) posA.push_back(it); else negA.push_back(it); } // Loop to iterate array B[] for (const auto& it : B) if (it >= 0) posB.push_back(it); else negB.push_back(it); // Stores the lower and upper bounds // of the binary search int l = LLONG_MIN, r = LLONG_MAX; // Stores the final answer int ans; // Find the kth smallest integer // using binary search while (l <= r) { // Stores the mid int mid = (l + r) / 2; // If the number of elements // greater than mid in product // array are more than K if (check(mid, posA, posB, negA, negB, K)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return answer return ans;}// Driver Codeint32_t main(){ vector<int> A = { -4, -2, 0, 3 }; vector<int> B = { 1, 10 }; int K = 7; cout << kthSmallestProduct(A, B, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if count of elements// greater than req in product array are// more than K or notstatic boolean check(int req, Vector<Integer> posA, Vector<Integer> posB, Vector<Integer> negA, Vector<Integer> negB, int K){ // Stores the count of numbers less // than or equal to req int cnt = 0; // Case with both elements of A[] and // B[] are negative int first = 0; int second = negB.size() - 1; // Count number of pairs formed from // array A[] and B[] with both elements // negative and there product <= req while (first < negA.size()) { while (second >= 0 && negA.elementAt(first) * negB.elementAt(second) <= req) second--; // Update cnt cnt += negB.size() - second - 1; first++; } // Case with both elements of A[] and // B[] are positive first = 0; second = posB.size() - 1; // Count number of pairs formed from // array A[] and B[] with both elements // positive and there product <= req while (first < posA.size()) { while (second >= 0 && posA.elementAt(first) * posB.elementAt(second) > req) second--; // Update cnt cnt += second + 1; first++; } // Case with elements of A[] and B[] // as positive and negative respectively first = posA.size() - 1; second = negB.size() - 1; // Count number of pairs formed from // +ve integers of A[] and -ve integer // of array B[] product <= req while (second >= 0) { while (first >= 0 && posA.elementAt(first) * negB.elementAt(second) <= req) first--; // Update cnt cnt += posA.size() - first - 1; second--; } // Case with elements of A[] and B[] // as negative and positive respectively first = negA.size() - 1; second = posB.size() - 1; // Count number of pairs formed from // -ve and +ve integers from A[] and // B[] with product <= req for (; first >= 0; first--) { while (second >= 0 && negA.elementAt(first) * posB.elementAt(second) <= req) second--; // Update cnt cnt += posB.size() - second - 1; } // Return Answer return (cnt >= K);}// Function to find the Kth smallest// number in array formed by product of// any two elements from A[] and B[]static int kthSmallestProduct(int[] A, int[] B, int K){ Vector<Integer> posA = new Vector<>(); Vector<Integer> negA = new Vector<>(); Vector<Integer> posB = new Vector<>(); Vector<Integer> negB = new Vector<>(); // Loop to iterate array A[] for (int it : A) { if (it >= 0) posA.add(it); else negA.add(it); } // Loop to iterate array B[] for (int it : B) if (it >= 0) posB.add(it); else negB.add(it); // Stores the lower and upper bounds // of the binary search int l = Integer.MIN_VALUE, r = Integer.MAX_VALUE; // Stores the final answer int ans=0; // Find the kth smallest integer // using binary search while (l <= r) { // Stores the mid int mid = (l + r) / 2; // If the number of elements // greater than mid in product // array are more than K if (check(mid, posA, posB, negA, negB, K)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return answer return ans;}// Driver Codepublic static void main(String[] args){ int[] A = { -4, -2, 0, 3 }; int[] B = { 1, 10 }; int K = 7; System.out.print(kthSmallestProduct(A, B, K));}}// This code is contributed by gauravrajput1 |
Python3
# python program for the above approachLLONG_MAX = 9223372036854775807LLONG_MIN = -9223372036854775807# Function to check if count of elements# greater than req in product array are# more than K or notdef check(req, posA, posB, negA, negB, K): # Stores the count of numbers less # than or equal to req cnt = 0 # Case with both elements of A[] and # B[] are negative first = 0 second = len(negB) - 1 # Count number of pairs formed from # array A[] and B[] with both elements # negative and there product <= req while (first < len(negA)): while (second >= 0 and negA[first] * negB[second] <= req): second -= 1 # Update cnt cnt += len(negB) - second - 1 first += 1 # Case with both elements of A[] and # B[] are positive first = 0 second = len(posB) - 1 # Count number of pairs formed from # array A[] and B[] with both elements # positive and there product <= req while (first < len(posA)): while (second >= 0 and posA[first] * posB[second] > req): second -= 1 # Update cnt cnt += second + 1 first += 1 # Case with elements of A[] and B[] # as positive and negative respectively first = len(posA) - 1 second = len(negB) - 1 # Count number of pairs formed from # +ve integers of A[] and -ve integer # of array B[] product <= req while (second >= 0): while (first >= 0 and posA[first] * negB[second] <= req): first -= 1 # Update cnt cnt += len(posA) - first - 1 second -= 1 # Case with elements of A[] and B[] # as negative and positive respectively first = len(negA) - 1 second = len(posB) - 1 # Count number of pairs formed from # -ve and +ve integers from A[] and # B[] with product <= req for first in range(first, -1, -1): while (second >= 0 and negA[first] * posB[second] <= req): second -= 1 # Update cnt cnt += len(posB) - second - 1 # Return Answer return (cnt >= K)# Function to find the Kth smallest# number in array formed by product of# any two elements from A[] and B[]def kthSmallestProduct(A, B, K): posA = [] negA = [] posB = [] negB = [] # Loop to iterate array A[] for it in A: if (it >= 0): posA.append(it) else: negA.append(it) # Loop to iterate array B[] for it in B: if (it >= 0): posB.append(it) else: negB.append(it) # Stores the lower and upper bounds # of the binary search l = LLONG_MIN r = LLONG_MAX # Stores the final answer ans = 0 # Find the kth smallest integer # using binary search while (l <= r): # Stores the mid mid = (l + r) // 2 # If the number of elements # greater than mid in product # array are more than K if (check(mid, posA, posB, negA, negB, K)): ans = mid r = mid - 1 else: l = mid + 1 # Return answer return ans# Driver Codeif __name__ == "__main__": A = [-4, -2, 0, 3] B = [1, 10] K = 7 print(kthSmallestProduct(A, B, K)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to check if count of elements // greater than req in product array are // more than K or not static bool check(int req, List<int> posA, List<int> posB, List<int> negA, List<int> negB, int K) { // Stores the count of numbers less // than or equal to req int cnt = 0; // Case with both elements of []A and // []B are negative int first = 0; int second = negB.Count - 1; // Count number of pairs formed from // array []A and []B with both elements // negative and there product <= req while (first < negA.Count) { while (second >= 0 && negA[first] * negB[second] <= req) second--; // Update cnt cnt += negB.Count - second - 1; first++; } // Case with both elements of []A and // []B are positive first = 0; second = posB.Count - 1; // Count number of pairs formed from // array []A and []B with both elements // positive and there product <= req while (first < posA.Count) { while (second >= 0 && posA[first] * posB[second] > req) second--; // Update cnt cnt += second + 1; first++; } // Case with elements of []A and []B // as positive and negative respectively first = posA.Count - 1; second = negB.Count - 1; // Count number of pairs formed from // +ve integers of []A and -ve integer // of array []B product <= req while (second >= 0) { while (first >= 0 && posA[first] * negB[second] <= req) first--; // Update cnt cnt += posA.Count - first - 1; second--; } // Case with elements of []A and []B // as negative and positive respectively first = negA.Count - 1; second = posB.Count - 1; // Count number of pairs formed from // -ve and +ve integers from []A and // []B with product <= req for (; first >= 0; first--) { while (second >= 0 && negA[first]* posB[second]<= req) second--; // Update cnt cnt += posB.Count - second - 1; } // Return Answer return (cnt >= K); } // Function to find the Kth smallest // number in array formed by product of // any two elements from []A and []B static int kthSmallestProduct(int[] A, int[] B, int K) { List<int> posA = new List<int>(); List<int> negA = new List<int>(); List<int> posB = new List<int>(); List<int> negB = new List<int>(); // Loop to iterate array []A foreach (int it in A) { if (it >= 0) posA.Add(it); else negA.Add(it); } // Loop to iterate array []B foreach (int it in B) if (it >= 0) posB.Add(it); else negB.Add(it); // Stores the lower and upper bounds // of the binary search int l = int.MinValue, r = int.MaxValue; // Stores the readonly answer int ans = 0; // Find the kth smallest integer // using binary search while (l <= r) { // Stores the mid int mid = (l + r) / 2; // If the number of elements // greater than mid in product // array are more than K if (check(mid, posA, posB, negA, negB, K)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return answer return ans; } // Driver Code public static void Main(String[] args) { int[] A = { -4, -2, 0, 3 }; int[] B = { 1, 10 }; int K = 7; Console.Write(kthSmallestProduct(A, B, K)); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to check if count of elements// greater than req in product array are// more than K or notfunction check(req, posA, posB, negA, negB, K){ // Stores the count of numbers less // than or equal to req let cnt = 0; // Case with both elements of A[] and // B[] are negative let first = 0; let second = negB.length - 1; // Count number of pairs formed from // array A[] and B[] with both elements // negative and there product <= req while (first < negA.length) { while (second >= 0 && negA[first] * negB[second] <= req) second--; // Update cnt cnt += negB.length - second - 1; first++; } // Case with both elements of A[] and // B[] are positive first = 0; second = posB.length - 1; // Count number of pairs formed from // array A[] and B[] with both elements // positive and there product <= req while (first < posA.length) { while (second >= 0 && posA[first] * posB[second] > req) second--; // Update cnt cnt += second + 1; first++; } // Case with elements of A[] and B[] // as positive and negative respectively first = posA.length - 1; second = negB.length - 1; // Count number of pairs formed from // +ve integers of A[] and -ve integer // of array B[] product <= req while (second >= 0) { while (first >= 0 && posA[first] * negB[second] <= req) first--; // Update cnt cnt += posA.length - first - 1; second--; } // Case with elements of A[] and B[] // as negative and positive respectively first = negA.length - 1; second = posB.length - 1; // Count number of pairs formed from // -ve and +ve integers from A[] and // B[] with product <= req for (; first >= 0; first--) { while (second >= 0 && negA[first] * posB[second] <= req) second--; // Update cnt cnt += posB.length - second - 1; } // Return Answer return cnt >= K;}// Function to find the Kth smallest// number in array formed by product of// any two elements from A[] and B[]function kthSmallestProduct(A, B, K) { let posA = [], negA = [], posB = [], negB = []; // Loop to iterate array A[] for (it of A) { if (it >= 0) posA.push(it); else negA.push(it); } // Loop to iterate array B[] for (it of B) if (it >= 0) posB.push(it); else negB.push(it); // Stores the lower and upper bounds // of the binary search let l = Number.MIN_SAFE_INTEGER, r = Number.MAX_SAFE_INTEGER; // Stores the final answer let ans; // Find the kth smallest integer // using binary search while (l <= r) { // Stores the mid let mid = (l + r) / 2; // If the number of elements // greater than mid in product // array are more than K if (check(mid, posA, posB, negA, negB, K)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } // Return answer return ans;}// Driver Codelet A = [-4, -2, 0, 3];let B = [1, 10];let K = 7;document.write(kthSmallestProduct(A, B, K));// This code is contributed by gfgking.</script> |
Output:
3
Time Complexity: O((N+M)*log 264) or O((N+M)*64)
Auxiliary Space: O(N+M)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
