StellarSpecter's blog

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

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

impossible

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

-is-this-fft-

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

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

Check this out

→ Reply