筆算の位ごとの置き場に積を足し、数字の文字列どうしを掛ける

数学と行列問題 149

10 進の数字だけでできた 2 つの文字列の積を、文字列で返します。大きい整数の型に直さず、桁どうしの積を筆算の位ごとの置き場に足し、最後に繰り上げをまとめる練習です。

海外で定番の問題リスト 4 本には入っていません

問題

電卓の道具で、とても長い数を扱います。0 以上の整数を 10 進で書いた文字列 a と b を受け取り、その積を 10 進の文字列で返す関数を書いてください。

数の型や大きい整数の型 (Python の int()、JavaScript の BigInt、Go の math/big など) に直さず、桁ごとに計算してください
a と b は数字だけでできていて、"0" のときを除き先頭は "0" ではありません
答えも、"0" のときを除き先頭に "0" を付けません
a と b の長さは 1 以上 200 以下です

入力と出力の例

例 1

a = "45" b = "12"

"540"

例 2

どちらかが 0 なら、答えは "0" です。"000" にはしません。

a = "999" b = "0"

"0"

例 3

途中に 0 の桁があっても、位はずれません。

a = "807" b = "96"

"77472"

面接での聞かれ方

面接では、桁の扱いと添え字の計算を見る問題として出されます。

「文字列で渡された 2 つの数を掛けてください。整数に変換してはいけません」
筆算のように、段ごとの足し算を作ってから全部を足す書き方を見せると、「途中の文字列を作らずにできますか？」と続きます
「答えは最大で何桁になりますか？」と聞かれることもあります

芯は、a の i 桁目と b の j 桁目の積が、答えのどの位に落ちるかを式で言えることです。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

小学校の筆算では、b の 1 桁ずつを a に掛けた段を作り、位をずらして全部を足します。正しく動きますが、段ごとの文字列と、文字列どうしの足し算が要り、書く量が増えます。

段 2

m 桁と n 桁の積は、多くても m + n 桁です。そこで、長さ m + n の整数の並び pos を答えの位の置き場として用意します。a の i 番目 (左から 0 で数える) と b の j 番目の桁の積は、pos の i + j + 1 番目に落ち、繰り上がりは i + j 番目へ行きます。

段 3

i と j を右から左へ回し、積に pos[i + j + 1] を足した和 s を作ります。s の一の位を pos[i + j + 1] に戻し、10 で割った商を pos[i + j] に足します。最後に先頭の 0 を飛ばして文字に並べ、全部が 0 なら "0" を返します。

解答

Python

def multiply_strings(a, b):
    m, n = len(a), len(b)
    pos = [0] * (m + n)
    for i in range(m - 1, -1, -1):
        x = ord(a[i]) - 48
        for j in range(n - 1, -1, -1):
            y = ord(b[j]) - 48
            s = x * y + pos[i + j + 1]
            pos[i + j + 1] = s % 10
            pos[i + j] += s // 10
    k = 0
    while k < m + n - 1 and pos[k] == 0:
        k += 1
    return "".join(
        str(d) for d in pos[k:]
    )

JavaScript

function multiplyStrings(a, b) {
  const m = a.length;
  const n = b.length;
  const pos = new Array(m + n).fill(0);
  for (let i = m - 1; i >= 0; i--) {
    const x = a.charCodeAt(i) - 48;
    for (let j = n - 1; j >= 0; j--) {
      const y = b.charCodeAt(j) - 48;
      const s = x * y + pos[i + j + 1];
      pos[i + j + 1] = s % 10;
      pos[i + j] += Math.floor(s / 10);
    }
  }
  let k = 0;
  while (
    k < m + n - 1 &&
    pos[k] === 0
  ) {
    k++;
  }
  return pos.slice(k).join("");
}

Go

func multiplyStrings(
	a, b string,
) string {
	m, n := len(a), len(b)
	pos := make([]int, m+n)
	for i := m - 1; i >= 0; i-- {
		x := int(a[i] - '0')
		for j := n - 1; j >= 0; j-- {
			y := int(b[j] - '0')
			s := x*y + pos[i+j+1]
			pos[i+j+1] = s % 10
			pos[i+j] += s / 10
		}
	}
	k := 0
	for k < m+n-1 && pos[k] == 0 {
		k++
	}
	out := make([]byte, 0, m+n-k)
	for _, d := range pos[k:] {
		out = append(out, byte('0'+d))
	}
	return string(out)
}

48 は文字 0 の番号です。pos[i + j] には一時的に 10 以上の値がたまることがありますが、次にその位を s に入れるときに一の位と繰り上がりに分かれます。いちばん左の pos[0] は、最後の繰り上がりを受けるだけなので 9 を超えません。

計算量

時間は O(m × n) です。桁の組ごとに 1 回ずつ掛けます
使う記憶は、答えの置き場の O(m + n) です
段ごとの文字列を作って足す書き方も時間は O(m × n) ですが、途中の文字列の分だけ記憶と手間が増えます

よくある間違い

数に直して掛ける。 200 桁は 64 ビットの整数にも、JavaScript の数にも入りません。条件で禁じられていなくても、20 桁を超えると答えが狂います
先頭の 0 を残す。例 1 では pos が [0, 5, 4, 0] になり、そのまま並べると "0540" です。先頭の 0 を飛ばします
0 を全部飛ばして空の文字列を返す。例 2 では pos が全部 0 です。最後の 1 桁は残すよう、k を m + n - 1 で止めます
積の落ちる位を間違える。 i + j に一の位を入れると、答えが 1 桁ずれます。一の位は i + j + 1、繰り上がりは i + j です

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def multiply_strings(a: str, b: str) -> str:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(multiply_strings("45", "12"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します