Multiply Strings - Practice Coding Problems

Multiply Strings - Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Input & Output

Example 1 — Basic Multiplication

$ Input: num1 = "2", num2 = "3"

› Output: "6"

💡 Note: Simple single digit multiplication: 2 × 3 = 6

Example 2 — Multi-digit Numbers

$ Input: num1 = "123", num2 = "456"

› Output: "56088"

💡 Note: Grade school multiplication: 123 × 456 = 56088 using digit-by-digit multiplication with carries

Example 3 — Zero Case

$ Input: num1 = "0", num2 = "9133"

› Output: "0"

💡 Note: Any number multiplied by zero equals zero

Constraints

1 ≤ num1.length, num2.length ≤ 200
num1 and num2 consist of digits only
Both num1 and num2 do not contain any leading zero, except the number 0 itself

Visualization

Tap to expand

Understanding the Visualization

Input

Two number strings that cannot be converted to integers

Process

Digit-by-digit multiplication with carry handling

Output

Product as a string without leading zeros

Key Takeaway

🎯 Key Insight: Use position-based multiplication where digits at positions i and j contribute to result position i+j, avoiding integer conversion

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to simulate grade school multiplication using arrays to handle large numbers without integer conversion. Best approach uses position-based multiplication where digits at positions i and j contribute to result position i+j. Time: O(n×m), Space: O(n+m)

Common Approaches

Approach	Time	Space	Notes
✓ Grade School Multiplication	O(n × m)	O(n + m)	Simulate manual multiplication using arrays to store intermediate results
Direct Conversion (Invalid)	O(n + m)	O(1)	Convert strings to integers, multiply, convert back

Grade School Multiplication — Algorithm Steps

Initialize result array with size n+m
For each digit in num2, multiply with each digit in num1
Handle carries and store partial products in correct positions
Convert result array back to string, removing leading zeros

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Initialize result array of size n+m

Multiply

Multiply each digit pair and handle carries

Convert

Convert result array back to string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* num1, char* num2) {
    if (strcmp(num1, "0") == 0 || strcmp(num2, "0") == 0) {
        char* result = malloc(2);
        strcpy(result, "0");
        return result;
    }
    
    int n = strlen(num1), m = strlen(num2);
    int* resultArr = calloc(n + m, sizeof(int));
    
    // Process from right to left
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            // Multiply current digits
            int product = (num1[i] - '0') * (num2[j] - '0');
            // Position in result array
            int pos1 = i + j, pos2 = i + j + 1;
            // Add to existing value
            int sum = product + resultArr[pos2];
            // Store units and carry
            resultArr[pos2] = sum % 10;
            resultArr[pos1] += sum / 10;
        }
    }
    
    // Convert result back to string
    char* result = malloc(n + m + 1);
    int index = 0, start = 0;
    
    // Skip leading zeros
    while (start < n + m && resultArr[start] == 0) {
        start++;
    }
    
    // Build result string
    for (int i = start; i < n + m; i++) {
        result[index++] = resultArr[i] + '0';
    }
    result[index] = '\0';
    
    free(resultArr);
    return index == 0 ? "0" : result;
}

int main() {
    char num1[1000], num2[1000];
    fgets(num1, sizeof(num1), stdin);
    fgets(num2, sizeof(num2), stdin);
    num1[strcspn(num1, "\n")] = 0;
    num2[strcspn(num2, "\n")] = 0;
    char* result = solution(num1, num2);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

Nested loops: outer loop iterates m digits of num2, inner loop iterates n digits of num1

✓ Linear Growth

Space Complexity

O(n + m)

Result array of size n+m to store all possible digit positions

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Grade School Multiplication — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler