Given two sorted arrays A and B and an integer number k, return the first k pair
ID: 3722271 • Letter: G
Question
Given two sorted arrays A and B and an integer number k, return the first k pairs from the set Ax B ordered by the sum of the elements. A x B-cartesian product, i.e. if A = {a1, , an) and B = {b1, b2, (a1, bn),....(an, bn-the set of A.length *B.length pairs. , bnj, Ax B = {(a1, b1), (a1, b2), , Testcase: input. A = {1, 2, 5), B = {2,4}, k = 4 output: (1, 2), (2, 2), (1, 4), (2, 4) Provide the solution (pseudocode or just a description of the method). Please, note that if A.length is large (say 1000) and B.length is large (say 1000), an implementation of your algorithm should still be able to handle the problem.Explanation / Answer
// java programm
public class arrayPairs {
//This programm will defenitely work for input >1000 numbers
public static void main(String[] args) {
int a[]={1,2,5}; //take input from console if you want
int b[]={2,4};
int k=4; //this is your input k
int len=a.length*b.length; // take 3 one dimentional arrays with a size of len
int c[]=new int[len];
int d[]=new int[len];
int sum[]=new int[len];
int s=0;
for(int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
c[s]=a[i]; //print one pair into two arrays(first element in first array and second element in second array)
d[s]=b[j];
sum[s]=a[i]+b[j]; //take sum into third array
s++;
}
}
int e[]=new int[len];
for(int i=0;i<len;i++)
e[i]=i; //take e array with index from 0 to len
for(int i=0;i<sum.length;i++)
{
for(int j=0;j<sum.length-1;j++)
{
if(sum[j]>sum[j+1])
{
int temp=e[j]; //When sorting the sum array, swap the index of e array.
e[j]=e[j+1];
e[j+1]=temp;
int temp2=sum[j];
sum[j]=sum[j+1];
sum[j+1]=temp2;
}
}
}
for(int i=0;i<k;i++)
{
System.out.printf("(%d,%d) ",c[e[i]],d[e[i]]);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.