2. [10 marks] You have a set of N coins in a bag, each having a value betweern 1

Question

2. [10 marks] You have a set of N coins in a bag, each having a value betweern 1 and M, where M 2 N. Some coins may have the same value. You pick two coins (without replacement) and record the sum of their values. Determine what possible sums can be achieved, in O(M log M) time. For example, if there are N 3 coins in the bag with values 1, 4 and 5 (so we could have M = 5), then the possible sums are 5, 6 and 9. Hint: if the coins have values vi,..., vv, how might you use the polynomial coins (without replacement) and record the sum of their milaes. Determine UN

Explanation / Answer

Dear Friend,

Consider the given example where we have three coins with 1, 4 and 5. You can represent it as a polynomial as   f(x) = x^1 + x^4 + x^5 where powers are the coin values.

Now if you compute f(x)*f(x) it would be

( x^1 + x^4 + x^5) * ( x^1 + x^4 + x^5) = x^2 + x^5 + x^6 + x^5 + x^8 + x^9+x^6 + x^9 + x^10 = x^2 + 2x^5 + 2x^6 + x^8 + 2x^9   + x^10

Places where the coefficient is greater then 1 are the result of choosing different coefficients. If you collect powers of the terms where coefficient is 2 are   5, 6, and 9 which is our answer.

So the solution is as below.

step-01: make a polynomial by placing all the coin values to the power of x. This step would take O(M) time.

step-02: Find square of the polynomial cumputed as above using FFT (fast fourier transform). It would take O(M log M) time

setp03: Print power of all the terms having coefficient greater then one (this is your answer). It would take O(M log M)

Overall running time is O(M log M)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.