Friday, July 08, 2016

Kth smallest sum form two sorted arrays

Given two integer arrays sorted in ascending order and an integer k. Define sum = a + b, where a is an element from the first array and b is an element from the second one. Find the kth smallest sum out of all possible sums. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 int getKthSmallest(int a[],int b[],int k){

    Objects.requireNonNull(a);

    Objects.requireNonNull(b);

    if(k<0||k>a.length || k>b.length)throw new RuntimeException("invalid input");

    return Math.min(a[k-1]+b[0],b[k-1]+a[0]); 

}

No comments: