Google Interview Question Software Engineer / Developers
the above solution will not work .
suppose by your method you reach A[1]A[2] and B[1]B[2].
by comapring the differences your next element will be either a[1]b[2] or a[2]b[1].
but what about a[1]b[1]
I am not getting what you are trying to say..lets run the above algo one more time..
suppose second pair we got is A[0],B[1]
Now we will again compare
if( A[0]-A[1] >=B[1] -B[2])
then pair is A[0],B[2]
else
pair is A[1],B[1]
we are getting A[1],B[1]...
when you got the second pair as A[0], B[1].then actually you are foregetting now a[1],b[0].
see a[1].b[0] may be less than a[0]b[1] but it may be more than a[0]b[2] definitely more than a[1],b[1]. see this problem as a two dimension matrix where each i,j corresponds to corresponding sum. you are excluding elements from diagonal from comparison.
Lets put val(a,b) in a matrix, such that X(i,j) is sum of a(i) + b (j).
Now for every X (i,j) there are i*j values which are less than X (i,j). X (m,n ) is < than X (i,j) if m<=j && m <=j;
so in Matrix we tranvers row wise
In First row there are n elements which can be part of our answer.
In Secnod row there are n/2 elements ...........
.
.
In Nth row there is 1 element....
So total number of elements which can be part of our answer is
N(1 +1/2 +1/3+............+1/n)
which is less than 2N.
once we collect all these elements we can sort them in nlogn or as we just have to find First n it can be done in even lesser time.
I came up an idea similar to Vishal. However, the summation of the harmonic series is O(nlogn) [REF: corman]
Now, to find n-th largest sum among O(nlogn) elements can be done in O(nlogn) time using the median-of-median finding order statistic method [REF: corman]
Finally finding the n largest sum-pairs can be done by comparing with n-th largest sum. So total running time is O(nlogn).
However, still O(n) solution seems quite hard to figure out.
Frederickson and Johnson's algorithm can find the kth element from the X+Y matrix. I guess with some adjustment, it is able to find the largest k elements.
This is the correct answer.
If you imagine an n by n matrix of the sums of each pairing of the arrays, the FJ algorithm can pick the Kth largest pair. It's that not easy to follow, but is described in section II of www dot ist.caltech.edu/~sthite/pubs/selectX+Y.pdf
If you dug in, you'd find that you can modify the algorithm, to keep track of which part of the n by n matrix that will have the K largest values, still in O(n) time.
Then you can iterate through the K values to compute and print them, which takes O(k) time, but because in this statement of the problem n==k, the overall runtime is O(n).
All of this said, most interviewers don't expect that you know or can derive this algorithm in an interview, but just that you can discuss possible solutions intelligently and pick up solutions with help.
I am assuming that the n output pairs have to be put in decreasing order [if the arrays are sorted in decreasing order] and vice versa. This is an O(n) solution:
count = 0;
put a[0]b[0] to output array;
count++;
check if count == n; if yes, exit;
i = 0;
while(1)
{
compare a[i+1]b[i] and a[i]b[i+1]
put max of the above comparison to output array; count++;
check if count == n; if yes, break;
put min of the above comparison to output array; count++;
check if count == n; if yes, break;
i++;
put a[i+1]b[i+1] to output array; count++;
check if count == n; if yes, break;
}
Oops, here's the above algo with better alignment.I am assuming that the n output pairs have to be put in decreasing order [if the arrays are sorted in decreasing order] and vice versa. This is an O(n) solution:
count = 0;
put a[0]b[0] to output array;
count++;
check if count == n; if yes, exit;
i = 0;
while(1)
{
compare a[i+1]b[i] and a[i]b[i+1];
put max of the above comparison to output array;count++;
check if count == n; if yes, break;
put min of the above comparison to output array; count++;
check if count == n; if yes, break;
i++;
put a[i+1]b[i+1] to output array; count++;
check if count == n; if yes, break;
}
What are you smoking? You should at least try some trivial test case before posting the code:
A {20, 4, 3, 1}
B {4, 3, 2, 1}
int i=0;
int j=0;
int count=n;
while(count--) {
print pair A[i], B[j]
if (A[i]+B[j+1] >= A[i+1]+B[j]) i++;
else j++;
}
static Tuple<int, int> mergedArray(int[] x, int[] y)
{
Tuple<int, int>[] mergedarray = new Tuple<int, int>[x.Length * y.Length];
int xi, yi, xj, yj;
xi = yi = yj = 0;
xj = 1;
int resultIndex = -1;
while (true)
{
resultIndex++;
if (xj >= x.Length)
{
mergedarray[resultIndex] = new Tuple<int, int>(x[xi], y[yi]);
yi++;
if (yi >= y.Length)
{
yi = 0;
xi++;
}
}
if (x[xi] + y[yi] > x[xj] + y[yj])
{
mergedarray[resultIndex] = new Tuple<int, int>(x[xi], y[yi]);
yi++;
if (yi >= y.Length)
{
yi = 0;
xi = Math.Max(xi + 1, xj + 1);
}
}
else
{
mergedarray[resultIndex] = new Tuple<int, int>(x[xj], y[yj]);
yj++;
if (yj >= y.Length)
{
yj = 0;
xj = Math.Max(xj + 1, xi + 1);
}
}
if (xi >= x.Length)
{
xi = xj;
yi = yj;
}
}
}
The idea here is to have two pairs (xi, yi) and (xj, yj) which always point to the next possible candidates in the array. O(n) time, O(1) space.
The code should also have logic to exit the loop after xi = x.length -1 and yi = y.length -1.
can be done in O(n/2)
First largest is A[n]+b[n] obviously.
Declare answer[n];
c=n;
answer[c]=A[n]+B[n];
for i=n-1 -> n/2
X=(A[n]+B[n-1]);
Y=(A[n-1]+B[n]);
answer[c--]= X => Y? X : Y
answer[c--]= X < Y? X : Y
end
a = {a_1, a_2, ..., a_n}
b = {b_1, b_2, ..., b_n}
first we have
pre_a = {0,a_1-a_2,a_2-a_3,...,a_{n-1} - a_n}
pre_b = {0,b_1-b_2,b_2-b_3,...,b_{n-1} - b_n}
First let answer[cnt] = a[0] + b[0], where cnt = 0.
Then starting with pre_a[i] and pre_b[j] where i = j = 1, do the following
if pre_a[i] <= pre_b[j]
answer[++cnt] = a[i] + b[j-1];
j = j+1;
else
answer[++cnt] = a[i - 1] + b[j];
i = i+1;
Keep doing above until cnt = n.
Seems, your method doesn't work for below input:
A = {100,89,75,52}
B = {71, 63,62, 48}
pre_A = {0, 11, 14, 23}
pre_B = {0, 8, 1, 14}
largest 4 sum = {100+71, 100+63, 100+62, 89+71 }
Your method skips 100+62 pair, because you increase 'i' just after comparing pre_a[i]>pre_b[j].
int count = 0;
int cnt11 = 0;
int cnt12 = 0;
int cnt22 = 0;
int cnt21 = 0;
while(count < a.length){
if(a[cnt11] + b[cnt12] > a[cnt21] + b[cnt22]){
System.out.println("a[" + cnt11 + "] + b[" + cnt12 + "]");
cnt12++;
if(cnt12 >= b.length){
cnt11++; cnt12 = cnt11;
}
} else if(a[cnt11] + b[cnt12] < a[cnt21] + b[cnt22]){
System.out.println("a[" + cnt21 + "] + b[" + cnt22 + "]");
cnt21++;
if(cnt21 >= a.length){
cnt22++; cnt21 = cnt22;
}
} else{
System.out.println("a[" + cnt11 + "] + b[" + cnt12 + "]");
cnt12++; cnt21++;
if(cnt12 >= b.length){
cnt11++; cnt12 = cnt11;
}
if(cnt21 >= a.length){
cnt22++; cnt21 = cnt22;
}
}
count++;
}
Read both array and create a n*n matrix, the entry in the matrix will be all the elements(a+b).the matrix will have the property of decreasing rows and decreasing columns.
Now generate n length sorted array from that matrix using k way merge sort.
here's an idea building on top of mayank and CC's discussion on IM:
consider example:
A[] = (15,10,9,7,5,3,2,1)
B[] = (20,17.13,8,6,4,3,0)
maintain two additional arrays A' and B' which store the cumulative difference from the highest value in A & B.
A'[] = (0,5,6,8,10,12,13,14)
B'[] = (0,3,7,12,14,16,17,20)
If I am thinking right, one of the highest elements in the two arrays must be present to form the largest k pairs. So, the first few largest elem pairs for A and B will be with difference 0,3,5,6,7,8,10 from maxsum(A[0]+B[0]).. Its like merging A' and B' with foll logic:
when next largest elem is A'[x], put (B[0],A[x]) as next largest pair.
when next largest elem is B'[x], put (A[0],B[x]) as next largest pair.
space complexity is O(n) and time complexity is O(n).
cant we do this as below:
a[]={a1,a2,....,an}; //a[i]>a[i+1]
b[]={b1,b2,....,bn}; //b[i]>b[i+1]
declare c[2n];
compute c[i] = a[0]+b[i]; i=0..n
ptr1=0;
j=i+1;
ptr2=j;
compute:c[j] = b[0]+a[i]; i=0..n
compare c[ptr1] and c[ptr2] to get the top n.
space=o(n), time=o(n)
Or am i missing anything.
Interviewer never mentioned that those pairs themselves need to be sorted. We should just print n pairs with largest values. And now here is the trick. Obviously, pairs will be selected like this
1 2 3 4
2 3 4
3 4
4
meaning that the smallest pair is number 1. Second and third are somewhere on diagonal 2. And the only diagonal when we start caring about order is the last one with number k, such that 1 + 2 + 3 + ... + k = n.
Obviously that diagonal can contain more numbers than we need, that is why we need to sort it. Sorting of it will take say... O(k*k), however k itself is O(sqrt(n)). It means that it will take O(n) to sort that last diagonal.
take an example:
A = {15, 14, 11, 7} and B = {13, 9, 5, 3}
take the difference between consecutive terms of sequence in these sequences, call resulting sequences as A' = {1, 3, 4} and B' = {4, 4, 2}
undoubtedly, the highest number is the sum of two biggest numbers- here it is 28, from (15, 13).
now which could be second one? either (15, 9), or (14, 13).
the second highest, by definition is the closest runner up to highest. so, if we see from difference arrays [which are A' and B'] we see closest one would be 1 less than 28, which is achieved if we consider (14, 13).
3rd largest could be definitely 4 less than 28- which is (15, 9).
4th largest would be, then (13, 11).
Isn't this problem pretty simple. Following is the algo:
1. the first elements of the arrays will always make the first pair.
2. Say we're at position i(in A) and j(in B)
The next candidates would be (a[i+1],b[j]) or (a[i],b[j+1]), chose the bigger one and increment the counter accordingly.
Please correct me if I m wrong
I think we can work out the solution as follows (refer to cubic's post above):-
A[] = (15,10,9,7,5,3,2,1)
B[] = (20,17.13,8,6,4,3,0)
maintain two additional arrays A' and B' which store the cumulative difference from the highest value in A & B.
A'[] = (0,5,6,8,10,12,13,14)
B'[] = (0,3,7,12,14,16,17,20)
The key points to note are:-
1.) The highest sum is A[0]+B[0]
2.) Now we need to remove either A[0] or B[0], and add A[1] or B[1]. The element we choose should be such that it leads to minimum reduction in the sum of A[0]+B[0]. This element will be the one corresponding to Min(A'[1], B'[1]) = B[1]. 2nd element = A[0] + B[1]
3.) To choose the the third element we follow similar logic and need to find the minimum of (A'[1],A'[2],B'[2]) = A[1]. 3rd element = A[1] + B[0]
4.) 4th element = min(A'[2], B'[2]) = A'[2].
-> A[2] + B[0]
And so on. Please share your comments
let a=[600, 500, 400, 300, 260, 220] and b = [200, 97, 50, 11, 10 , 3].For this A = [0,100,200,300,340,380] and B = [1,103,150,189,190, 197] The largest numbers are 800,700, 697, 650,600, 550 and so on. Please fit ur algo for this series up to first 6 largest nos. I am not able to follow ur algo for this series. Help me out. Also change the a[0] from 200 to 100 and try to fit ur algo.
Can't we first decide the largest n1 elements in array A, and the largest n2 elements in Array B, and n1*n2 is the smallest number bigger than n.
After that, we generate all possible values from the n1 and n2 "small array", then sort these values?
Although this is in O(nlogn), but this is correct, isn't it?
a=[600, 500, 400, 300, 260, 220] and b = [200, 97, 50, 11, 10 , 3].
1. take diff of each element from first element and create new dummy arrays
For this A' = [0,100,200,300,340,380] and B' = [0,103,150,189,190,197]
2. now based on diffs, create pairs
first pair = 600, 200
A'[1] < B'[1] => choose A'[1] and go to first (i.e zeroth) element of B.
2nd pair = 500, 200
A'[2] > B'[1] => choose A[0] & B[1]
3rd pair = 600, 97
A'[2] > B'[2] => choose A[0] & B[2]
4th = 600, 50
A'[2] > B'[3] => choose A[0] & B[3]
5th = 600, 11
lly, 6th = 600, 10;
A'[2] > B'[5] => choose A[0] & B[5] 7th = 600, 3
now choose A[1], B[1]
I think the solution is possible in O(n).
The resulting array will have following property:
-------------------------
|Largest | IN Between |
-------------------------
|In Between| Smallest |
-------------------------
With that in mind, I guess the sub-problem becomes find largest n element from X by X array. where X^2 >= n and (X-1)^ < n; i.e. first second arrays index is bound to X. Now you got O(n) elements some are extra. Now you can keep on doing quick partition. until to get a pivot at location 'n' btw, you only need to partition one side unlike quick sort as end result does not required to be sorted.
int x = (int)sqrt((double)(n));
if (x * x < n) ++x;
int * cadidate = new int [x*x];
int cadidateI = 0;
// O(n) loop.
for (int i = 0; i < x; ++i)
for (int j = 0; j < x; ++j)
candidate[i*x+j] = a[i] + b[j];
int candidateSize = x * x;
int *partitionArr = candidate;
int partSize = candidateSize;
/// n + n/2 + n/4 .... = O(n)
while (1)
{
int pivot = partitionArr[partSize - 1];
int large = 0;
int small = partSize - 2;
while (large < small)
{
if (partitionArr[large] >= pivot) ++large;
else if (partitionArr[small] < pivot) --small;
else
{
int temp = partitionArr[large];
partitionArr[large] = partitionArr[small];
partitionArr[small] = temp;
}
}
partitionArr[partSize - 1] = partitionArr[small];
partitionArr[small] = pivot;
int t = candidate - &partitionArr[small];
if (t == n) {break;}
else if (t < n)
{
partitionArr += (small + 1);
partSize -= (small + 1);
}
else
{
partSize = (small - 1);
}
}
// O(n) output time.
output first 'n' values from cadidate array.
[Input]
int []a = { 600, 500, 400, 300, 260, 220 }
int []b = { 200, 97, 50, 11, 10, 3 }
[Output]
800 700 697 650 611.
It can be handled as O(n). Let i, j are indexes for each array. At the first time, i=0, j=0 so a[i] + b[j] = 800. It is oblivious that a[0] + b[0] is the biggest sum value. Next biggest value will be a[1] + b[0] = 700. The interesting point is the third biggest value. As you see the output values, it is 697. Thus, i should be 0 and j should be 1. On the other hand, we should care about movement moving of index i and j.
Since i, j can be moved forward and backward, there are 9 possible sum for next biggest value : [i-1][j-1], [i-1][j], [i-1][i+1], [i][j-1], [i][j], [i][j+1], [i+1],[j-1], [i+1][j], [i+1][j+1]. Thus, finding the next biggest value from these values is the key idea. The number of possible values is 9 so that it needs O(9n) = O(n).
{{
public static int sum(int[] a, int[] b, int a_idx, int b_idx)
{
if (a_idx < 0 || b_idx < 0 || a_idx > a.length || b_idx > b.length)
{
return -1;
}
else
{
return a[a_idx] + b[b_idx];
}
}
public static void main(String[] args)
{
// Output : 800 700 697 650 611
int[] a = { 600, 500, 400, 300, 260, 220 };
int[] b = { 200, 97, 50, 11, 10, 3 };
int n = a.length;
int i = 0, j = 0;
for (int k = 1; k < n; k++)
{
int lastMaxValue = a[i] + b[j];
System.out.print(lastMaxValue + " ");
int[] sumValues = new int[9];
// sumValues[0] = sum(a, b, i - 1, j - 1);//It was already used as MaxValue in the past.
sumValues[1] = sum(a, b, i - 1, j);
sumValues[2] = sum(a, b, i - 1, j + 1);
sumValues[3] = sum(a, b, i, j - 1);
// sumValues[4] = sum(a, b, i, j);//It was the lastMaxValue. Don't have to compute again
sumValues[5] = sum(a, b, i, j + 1);
sumValues[6] = sum(a, b, i + 1, j - 1);
sumValues[7] = sum(a, b, i + 1, j);
sumValues[8] = sum(a, b, i + 1, j + 1);
// Find Max Position
int maxValue = 0, maxPos = -1;
for (int t = 0; t < sumValues.length; t++)
{
if (sumValues[t] > maxValue && sumValues[t] < lastMaxValue)
{
maxValue = sumValues[t];
maxPos = t;
}
}
// Update i or j according to MaxPos
i = i + (maxPos / 3 - 1);
j = j + (maxPos % 3 - 1);
}
}
}}
[Input]
int []a = { 600, 500, 400, 300, 260, 220 }
int []b = { 200, 97, 50, 11, 10, 3 }
[Output]
800 700 697 650 611.
It can be handled as O(n). Let i, j are indexes for each array. At the first time, i=0, j=0 so a[i] + b[j] = 800. It is oblivious that a[0] + b[0] is the biggest sum value. Next biggest value will be a[1] + b[0] = 700. The interesting point is the third biggest value. As you see the output values, it is 697. Thus, i should be 0 and j should be 1. On the other hand, we should care about movement moving of index i and j.
Since i, j can be moved forward and backward, there are 9 possible sum for next biggest value : [i-1][j-1], [i-1][j], [i-1][i+1], [i][j-1], [i][j], [i][j+1], [i+1],[j-1], [i+1][j], [i+1][j+1]. Thus, finding the next biggest value from these values is the key idea. The number of possible values is 9 so that it needs O(9n) = O(n).
public static int sum(int[] a, int[] b, int a_idx, int b_idx)
{
if (a_idx < 0 || b_idx < 0 || a_idx > a.length || b_idx > b.length)
{
return -1;
}
else
{
return a[a_idx] + b[b_idx];
}
}
public static void main(String[] args)
{
// Output : 800 700 697 650 611
int[] a = { 600, 500, 400, 300, 260, 220 };
int[] b = { 200, 97, 50, 11, 10, 3 };
int n = a.length;
int i = 0, j = 0;
for (int k = 1; k < n; k++)
{
int lastMaxValue = a[i] + b[j];
System.out.print(lastMaxValue + " ");
int[] sumValues = new int[9];
// sumValues[0] = sum(a, b, i - 1, j - 1);//It was already used as MaxValue in the past.
sumValues[1] = sum(a, b, i - 1, j);
sumValues[2] = sum(a, b, i - 1, j + 1);
sumValues[3] = sum(a, b, i, j - 1);
// sumValues[4] = sum(a, b, i, j);//It was the lastMaxValue. Don't have to compute again
sumValues[5] = sum(a, b, i, j + 1);
sumValues[6] = sum(a, b, i + 1, j - 1);
sumValues[7] = sum(a, b, i + 1, j);
sumValues[8] = sum(a, b, i + 1, j + 1);
// Find Max Position
int maxValue = 0, maxPos = -1;
for (int t = 0; t < sumValues.length; t++)
{
if (sumValues[t] > maxValue && sumValues[t] < lastMaxValue)
{
maxValue = sumValues[t];
maxPos = t;
}
}
// Update i or j according to MaxPos
i = i + (maxPos / 3 - 1);
j = j + (maxPos % 3 - 1);
}
}
[Input]
int []a = { 600, 500, 400, 300, 260, 220 }
int []b = { 200, 97, 50, 11, 10, 3 }
[Output]
800 700 697 650 611.
It can be handled as O(n). Let i, j are indexes for each array. At the first time, i=0, j=0 so a[i] + b[j] = 800. It is oblivious that a[0] + b[0] is the biggest sum value. Next biggest value will be a[1] + b[0] = 700. The interesting point is the third biggest value. As you see the output values, it is 697. Thus, i should be 0 and j should be 1. On the other hand, we should care about movement moving of index i and j.
Since i, j can be moved forward and backward, there are 9 possible sum for next biggest value : [i-1][j-1], [i-1][j], [i-1][i+1], [i][j-1], [i][j], [i][j+1], [i+1],[j-1], [i+1][j], [i+1][j+1]. Thus, finding the next biggest value from these values is the key idea. The number of possible values is 9 so that it needs O(9n) = O(n).
public static int sum(int[] a, int[] b, int a_idx, int b_idx)
{
if (a_idx < 0 || b_idx < 0 || a_idx > a.length || b_idx > b.length)
{
return -1;
}
else
{
return a[a_idx] + b[b_idx];
}
}
public static void main(String[] args)
{
// Output : 800 700 697 650 611
int[] a = { 600, 500, 400, 300, 260, 220 };
int[] b = { 200, 97, 50, 11, 10, 3 };
int n = a.length;
int i = 0, j = 0;
for (int k = 1; k < n; k++)
{
int lastMaxValue = a[i] + b[j];
System.out.print(lastMaxValue + " ");
int[] sumValues = new int[9];
// sumValues[0] = sum(a, b, i - 1, j - 1);//It was already used as MaxValue in the past.
sumValues[1] = sum(a, b, i - 1, j);
sumValues[2] = sum(a, b, i - 1, j + 1);
sumValues[3] = sum(a, b, i, j - 1);
// sumValues[4] = sum(a, b, i, j);//It was the lastMaxValue. Don't have to compute again
sumValues[5] = sum(a, b, i, j + 1);
sumValues[6] = sum(a, b, i + 1, j - 1);
sumValues[7] = sum(a, b, i + 1, j);
sumValues[8] = sum(a, b, i + 1, j + 1);
// Find Max Position
int maxValue = 0, maxPos = -1;
for (int t = 0; t < sumValues.length; t++)
{
if (sumValues[t] > maxValue && sumValues[t] < lastMaxValue)
{
maxValue = sumValues[t];
maxPos = t;
}
}
// Update i or j according to MaxPos
i = i + (maxPos / 3 - 1);
j = j + (maxPos % 3 - 1);
}
}
A O(n) algorithm is as follows.
==================================
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int *preprocess_array(int *a, int len);
void print_array(int *a, int len);
int main(int argc, char *argv) {
int n = 4;
int a[] = {33,22,11,1};
int b[] = {1111,111,110,105};
int cnt = 0;
int idx_a = 0;
int idx_b = 0;
int *answer = (int*)calloc(n,sizeof(int));
if (a[n - 1] >= b[0]) {
answer = a;
goto finish;
}
if (b[n - 1] >= a[0]) {
answer = b;
goto finish;
}
int *pre_a = preprocess_array(a,n);
int *pre_b = preprocess_array(b,n);
answer[cnt++] = a[idx_a] + b[idx_b];
while (cnt < n) {
if (pre_a[idx_a+1] <= pre_b[idx_b+1]) {
answer[cnt++] = a[++idx_a] + b[idx_b];
} else {
answer[cnt++] = a[idx_a] + b[idx_b];
}
}
finish:
print_array(answer,n);
cout << "Program ends!" << endl;
return 0;
}
int *preprocess_array(int *a, int len) {
int *b = (int *)calloc(len,sizeof(int));
b[0] = 0;
for (int i = 0; i < len - 1; i++) {
b[i + 1] = a[i] - a[i + 1];
}
return b;
}
void print_array(int *a, int len) {
for (int i = 0; i < len ; i++)
cout << a[i] << endl;
return;
}
==================================
a better view
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int *preprocess_array(int *a, int len);
void print_array(int *a, int len);
int main(int argc, char *argv) {
int n = 4;
int a[] = {33,22,11,1};
int b[] = {1111,111,110,105};
int cnt = 0;
int idx_a = 0;
int idx_b = 0;
int *answer = (int*)calloc(n,sizeof(int));
if (a[n - 1] >= b[0]) {
answer = a;
goto finish;
}
if (b[n - 1] >= a[0]) {
answer = b;
goto finish;
}
int *pre_a = preprocess_array(a,n);
int *pre_b = preprocess_array(b,n);
answer[cnt++] = a[idx_a] + b[idx_b];
while (cnt < n) {
if (pre_a[idx_a+1] <= pre_b[idx_b+1]) {
answer[cnt++] = a[++idx_a] + b[idx_b];
} else {
answer[cnt++] = a[idx_a] + b[idx_b];
}
}
finish:
print_array(answer,n);
cout << "Program ends!" << endl;
return 0;
}
int *preprocess_array(int *a, int len) {
int *b = (int *)calloc(len,sizeof(int));
b[0] = 0;
for (int i = 0; i < len - 1; i++) {
b[i + 1] = a[i] - a[i + 1];
}
return b;
}
void print_array(int *a, int len) {
for (int i = 0; i < len ; i++)
cout << a[i] << endl;
return;
}
if it is in decreasing order, then first pair is (A[0],B[0]).
- Anonymous May 03, 2010for next n-1 pairs, check the difference between A[0] and A[1] & B[0] and B[1].
if(A[0]-A[1] >= B[0] -B[1])
then pair is A[0],B[1]
else
A[1],B[0]
repeat this n-1 times , which will take O(n) time.....