C++で1を加算して末尾のゼロを削除し、Nから生成できる一意の数値の個数を数える方法

整数 N が与えられます。N に対して次の 2 つの操作を繰り返し適用し、その過程で生成される一意の数値の個数を求めます。手順は以下のとおりです。

• 数値に 1 を加算する

• 生成された数値の末尾にあるゼロを削除する(存在する場合)

たとえば N が 8 の場合、生成される数値は次のようになります。

操作 1 を適用:8 → 9

操作 2 を適用:9 に 1 を加えると 10 となり、末尾の 0 を削除して 1 になります

操作 1 を適用:2 → 3 → 4 → 5 → 6 → 7 → 8(ここで元の数列に戻る)

したがって、一意の数値の個数は 9 となります。

入出力例

例 1

入力:

N=21

出力:

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 18

説明:

生成される数値:21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3 --- 以降は同じ数列が繰り返される
一意の数値は 18 個

例 2

入力:

N=38

出力:

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 11

説明:

生成される数値:38, 39, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4 --- 以降は同じ数列が繰り返される
一意の数値は 11 個

アルゴリズムの考え方

このアプローチでは、操作 1 と操作 2 を適用した結果として生成されるすべての一意の数値を格納する unordered_set(順序なし集合)を作成します。数値が重複した時点で処理を停止し、最終的なセットのサイズが一意の数値の個数となります。

1. 数値 N を整数として受け取ります。
2. 生成された数値を格納するための unordered_set<int> 型の U_S を用意します。
3. 関数 unique_N(unordered_set<int>& U_S, int N) は、セットと N を受け取り、セット内の数値がすべて一意である間、数値を U_S に追加し続けます。
4. U_S.count(N) が 1 を返す場合、N はすでにセットに存在することを意味します。この場合、数値が重複し始めるため、関数から戻ります。
5. それ以外の場合は、N をセットに挿入し、操作 1(1 を加算)を適用します。
6. 数値 N に末尾のゼロがあるかどうか(10 の倍数かどうか)を確認します。
7. N % 10 が 0 の場合、10 で割ることで末尾のゼロを削除します。
8. 更新された N を引数として関数 unique_N() を再帰的に呼び出します。
9. 関数から戻った後、セット U_S のサイズを一意の数値の個数として取得します。
10. 結果として個数を出力します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
void unique_N(unordered_set<int>& U_S, int N){
    if (U_S.count(N)){
        return;
    }
    U_S.insert(N);
    N = N + 1;
    while (N % 10 == 0){
        N = N / 10;
    }
    unique_N(U_S, N);
}
int main(){
    int N = 7;
    unordered_set<int> U_S;
    unique_N(U_S, N);
    int count = U_S.size();
    cout << "Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: " << count;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count of unique numbers that can be generated from N by adding one and removing trailing zeros are: 9

まとめ

この問題は、unordered_set を使って生成済みの数値を管理することで効率的に解くことができます。数値が再び現れた時点でサイクルが検出され処理が終了するため、セットのサイズがそのまま答えになります。計算量は、操作を繰り返して生成される一意の数値の個数に依存します。