StellarSpecter's blog

Help me with this easy multiplication problem
By StellarSpecter, history, 4 months ago, In English

Given two numbers represented as strings a and b, compute their product and output product as a string.

|a| <=1e6, |b|<=1e6

How do I solve it, I brute forced it and it gives me TLE.

can anyone help me? is there an optimal way ??

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

impossible

→ Reply
»
4 months ago, # |
  Vote: I like it +21 Vote: I do not like it

-is-this-fft-

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So we have $$$10^{10^6} \cdot 10^{10^6} = 10^{2000000}$$$ , bro go create some new structure for such numbers

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a n^2 solution but it also gives a TLE under these constraints. can you send the problem link?

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Using FFT it can be solved in O(nlogn), n = max ( | a | , | b | ).

Check this out

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is FFT can anyone explain or is this a bluff and the problem is unsolvable ?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by StellarSpecter (previous revision, new revision, compare).

→ Reply