C++で配列として表現された数値に1を加算する方法

配列で表現された数値とは

数値を配列として表現する場合、数値の各桁を配列の個々の要素に格納します。配列の長さは数値の桁数と一致し、たとえば4桁の数値であれば配列の長さも4となります。各要素には一桁の数字（0〜9）だけが格納され、配列の末尾の要素には数値の最下位桁が、先頭の要素には最上位桁が保存されます。

例えば、数値351932は {3,5,1,9,3,2} という形で表現されます。

1を加算する仕組み

このような数値に1を加算するには、まず配列の最後の要素に1を足し、繰り上がり（キャリー）が発生するかどうかを確認します。最後の桁が9だった場合には繰り上がりが発生し、その要素の値は0になります。

繰り上がりが発生した場合は、その直前の(n-1番目の)要素に1を加え、さらにそこでも繰り上がりが起きていないかを確認します。例えば、{3,5,7,9} に1を加えると {3,5,8,0} となります。この例では繰り上がりが伝播し、7が8に変わっています。

アルゴリズムの手順

1. 配列の末尾の要素に1を加算します。
2. その値を10で割った商を繰り上がりとして求め、10で割った余りを新しい桁の値とします。
3. 繰り上がりが残っている限り、前方の要素に対して同じ処理を繰り返します。
4. すべての桁を処理してもなお繰り上がりが残る場合（例：999に1を加えるケース）、配列の先頭に1を挿入して桁を一つ増やします。

サンプルコード

#include <bits/stdc++.h>
using namespace std;

void addone(vector<int> &a) {
    int n = a.size();
    a[n-1] += 1;
    int carry = a[n-1] / 10;
    a[n-1] = a[n-1] % 10;
    for (int i = n-2; i >= 0; i--) {
        if (carry == 1) {
            a[i] += 1;
            carry = a[i] / 10;
            a[i] = a[i] % 10;
        }
    }
    if (carry == 1)
        a.insert(a.begin(), 1);
}

int main() {
    vector<int> num{2, 3, 9, 9};
    cout << "元の数値 : ";
    for (int i = 0; i < num.size(); i++)
        cout << num[i];
    cout << endl;
    addone(num);
    cout << "1を加算した後の数値 : ";
    for (int i = 0; i < num.size(); i++)
        cout << num[i];
    return 0;
}

出力結果

元の数値 : 2399
1を加算した後の数値 : 2400

コードのポイント

このプログラムでは、まず a[n-1]（最下位桁）に1を加え、10で割った結果から繰り上がりを判定しています。続くループでは、繰り上がりが存在する間だけ前方の桁へ処理を伝播させます。全桁を処理しても繰り上がりが残るケース（すべての桁が9の場合）には、a.insert() を使って先頭に新たな桁「1」を追加することで、正しい結果を保証しています。

計算量は最悪でも配列の全要素を一度走査するだけで済むため、O(n) となり、大きな桁数の数値にも効率的に対応できます。