StellarSpecter's blog

Help me with this easy multiplication problem
By StellarSpecter, history, 2 hours 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
  • -9
  • Vote: I do not like it

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

impossible

→ Reply
»
2 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

-is-this-fft-

→ Reply
»
2 hours 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
»
2 hours 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
»
2 hours ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

Check this out

→ Reply