thierrys
BAN USERInteresting problem that kept me busy some time but the trick is that arrays are sorted so, given a[0]+b[0] is for sure the first number that is to be produced, what are the next possible sums, well:
- S1 = a[a_i+1] + b[b_i];
- S2 = a[a_i+1] + b[0];
- S3 = a[a_i] + b[b_i+1];
- S4 = a[0] + b[b_i+1];
as you want to iterate over each arrays always checking the sum result of the other first array element when you increment either A index or B index. The smallest sum of the above for is the next one given that you:
- discard any sum smaller than the previous generated sum
- does not go beyond array boundaries
resulting code passing all the test series in this page is:
#include <stdio.h>
void print_Kth_min(int a[], int b[], int K, int N)
{
int a_i = 0, b_i = 0;
int count = 0;
int sum = 0;
sum = a[a_i] + b[b_i];
printf("[%d]+[%d] %d\n", a_i, b_i, sum);
while (count < K) {
/* Create the 4 possible next sum */
int S1 = a[a_i+1] + b[b_i];
int S2 = a[a_i+1] + b[0];
int S3 = a[a_i] + b[b_i+1];
int S4 = a[0] + b[b_i+1];
/*
Select the smallest one ensuring that:
- it needs to be bigger than latest generated sum (otherwise it has been made up already)
- does not goes beyond the array boundaries
*/
if ((S1 >= sum) && (a_i+1 < N) &&
((S2 < sum ? 1 : S1 <= S2)) &&
((S3 < sum ? 1 : S1 <= S3)) &&
((S4 < sum ? 1 : S1 <= S4))) {
a_i++;
} else if ((S2 >= sum) && (a_i+1 < N) &&
((S1 < sum ? 1 : S2 <= S1)) &&
((S3 < sum ? 1 : S2 <= S3)) &&
((S4 < sum ? 1 : S2 <= S4))) {
a_i++; b_i = 0;
} else if ((S3 >= sum) && (b_i+1 < N) &&
((S1 < sum ? 1 : S3 <= S1)) &&
((S2 < sum ? 1 : S3 <= S2)) &&
((S4 < sum ? 1 : S3 <= S4))) {
b_i++;
} else if ((S4 >= sum) && (b_i+1 < N) &&
((S1 < sum ? 1 : S4 <= S1)) &&
((S2 < sum ? 1 : S4 <= S2)) &&
((S3 < sum ? 1 : S4 <= S3))) {
b_i++; a_i = 0;
} else {
/* We've reached array's limits and need to finish iterating the one not reached yet */
if (a_i+1 == N) {
if (b_i+1 == N) {
/* K is greater than values we can make up */
return;
} else {
b_i++;
}
} else {
a_i++;
}
}
sum = a[a_i] + b[b_i];
printf("[%d]+[%d] %d\n", a_i, b_i, sum);
count ++;
}
}
int main(int argc, char *argv[])
{
int a1[] = { 1, 50, 100, 1000, 6000, 6002, 6004, 6006, 6008, 6010 };
int b1[] = {100, 200, 300, 2000, 3000, 4000, 5000, 6000, 7000, 8000 };
printf("Test 1\n");
print_Kth_min(a1, b1, 50, 10);
int a2[] = { 1, 6, 7, 9, 10, 14 };
int b2[] = { 2, 3, 5, 8, 11, 16 };
printf("Test 2\n");
print_Kth_min(a2, b2, 30, 6);
int a3[] = { 1, 30, 35 };
int b3[] = { 5, 6, 50 };
printf("Test 3\n");
print_Kth_min(a3, b3, 10, 3);
int a4[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10, 11};
int b4[] = { 1, 20, 30, 40, 50, 60, 70, 80, 90,100};
printf("Test 4\n");
print_Kth_min(a4, b4, 100, 10);
return 0;
}
You are write if was focused on making it simple but turns out that in case you have multiple time the same number it even gets into a locking situation:
does not produce at all the expected result !!
- thierrys December 21, 2013