56. Karatsuba Multiplication

Hard

Topics

Helpful tools to learn & understand

Watch key transitions, pointers, and variables update step-by-step.

Open

Read clean, documented implementations across multiple patterns.

View Code

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Input: x = 1234, y = 5678

Output: 7006652

Explanation: 1234 * 5678 = 7006652. The algorithm should correctly calculate this product.

Input: x = 12, y = 34

Output: 408

Explanation: 12 * 34 = 408. Testing with smaller numbers to verify correctness.

Input: x = 123456789, y = 987654321

Output: 121932631112635269

Explanation: Testing with large numbers to ensure the algorithm handles large inputs correctly.

Input: x = 1, y = 999999999

Output: 999999999

Explanation: Testing with '1' as one of the inputs.

Time Complexity

O(n^1.58)

Space Complexity

O(n)