Katkat
Back

Implement string-based big integer multiplication

PinterestSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Implement multiplyStrings(a, b) to multiply two non-negative integers given as decimal strings, returning the product as a string without any big-integer or arbitrary-precision library. The solution covers grade-school O(n*m) long multiplication with linear memory, the Karatsuba and FFT/NTT scaling alternatives, correct carry and leading/trailing-zero handling, and a full edge-case test plan.

Question

Implement multiplyStrings(a, b) to multiply two non-negative integers given as decimal strings and return their product as a decimal string. You may not convert the full inputs to a built-in big-integer or fixed-width integer type, nor use any arbitrary-precision arithmetic library.

Your solution must:

  1. Correctly multiply two non-negative integers represented as decimal strings and return the product as a string.
  2. Handle edge cases: "0" (and any product that is zero), "1", inputs of very different lengths, leading zeros in the inputs, and many trailing zeros. The result must not carry spurious leading zeros (e.g. "00" should never be returned).
  3. Scale efficiently to very large inputs (e.g. strings up to a few thousand digits, or up to ~10^5 total digits) while managing carries correctly and avoiding quadratic memory blowups.
  4. Discuss the algorithmic options and their trade-offs: grade-school long multiplication (O(n·m) time), Karatsuba (O(n^1.585)), and FFT/NTT-based convolution (O(n log n)). Implement at least one approach.
  5. State the time and space complexity of your implementation.
  6. Explain how you would test the solution, enumerating the edge cases above.