Form all possible unique sums and all ways to compute them by choosing and adding elements from two arrays

Правка en2, от saketag007, 2019-01-30 22:44:45

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

Теги #dp, #array, time complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский saketag007 2019-01-30 22:44:45 2 Tiny change: 'Ai,Bi<=10^9\n\nSample' -> 'Ai,Bi<=10^6\n\nSample'
en1 Английский saketag007 2019-01-30 13:44:54 925 Initial revision (published)