Given two arrays A and B of size n and m respectively. We can choose an element from A and one from B such that C=Ai + Bj . We have to compute all possible ways to from a sum C and also all unique sums.
Constraints:-
0<A,B<=10^5 // Size of array A and B
0<=Ai,Bi<=10^6
Sample I/P:-
2 3 //Size of array A and B
5 6 // Elements of array A
2 2 3 //Elements of array B
Sample O/P:-
7 2
8 3
9 1
Explanation:- 7 can be formed in two ways by A1+B1 , A1+B2 (using 1-based indexing)
8 can be formed in 3 ways by A1+B2 , A2+B1 , A2+B2
9 can be formed in 1 way by A2+B3
Please help me with a solution less than (n*m).
Have a look on my code:- Link here
Is there any other constrain on the problem? In worst case there could be n * m distinct sums and the time complexity just to output them would be O(n * m).
This problem is the most basic application of FFT. Consider two polynomails p1(x) = x^a1 + x^a2 + .. + x^an and p2(x) = x^b1 + x^b2 + ... + x^bm. Multiplying these polynomials would give your answer. Multiplication can be done using fft. Say after multiplication, you get p3(x) = c0 + c1*x + c2*x^2 + ... + ck*x^k. Coefficient of x^k will give you the number of ways to get k as a sum.
This would have been correct if values in the arrays A and B were small, but unfortunately Ai, Bi ≤ 109.
Oh sry, I read A,B <= 10^5 and thought these were the coefficients. My bad!
The values are upto 10^6 , sorry about the wrong constraints. Thank you for the approach.
Is this from Codechef's certification exam? In that case the constraint was
0<=Ai,Bi<=10^6
My solution was the same as mentioned by aviroop123 and it gave 100 points.
That's impossible. Consider following example:
Ai = i, Bi = M * i, where M = 104. You have to write at least 2 * 109 numbers. Obviously that's impossible within 4s.