StellarSpecter's blog

Help me with this easy multiplication problem
By StellarSpecter, history, 2 years 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

Comments Comments (4)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

-is-this-fft-

→ Reply
»
2 years ago, hide # |
 
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 years ago, hide # |
← 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