C++で文字列に変換せずに数値のすべての部分文字列を出力する方法

問題概要

この問題では、整数 n が与えられます。その数値から作成できるすべての部分文字列（連続する桁の並び）を出力することが求められます。ただし、文字列への変換は禁止されているため、整数を文字列や配列に変換して処理することはできません。

まず、具体例を見てみましょう。

入力: number = 5678
出力: 5, 56, 567, 5678, 6, 67, 678, 7, 78, 8

ご覧のとおり、先頭の桁から始まるすべての連続部分列が出力されています。

解決のアプローチ

この問題を解くには、数学的なロジックを活用します。基本的な考え方は、最上位桁から順に出力し、その後、下位の桁についても同様の処理を繰り返すというものです。除算と剰余演算を組み合わせることで、文字列変換なしに各桁へアクセスできます。

アルゴリズム

1. ステップ1: 数値の桁数に基づいて、対応する10のべき乗を計算します。
2. ステップ2: 数値を10のべき乗で割った商（先頭からの桁並び）を出力し、べき乗を10で割りながら、べき乗が0になるまで繰り返します。
3. ステップ3: 剰余演算で数値の最上位桁（MSB）を取り除き、新しい数値に対してステップ2を再度実行します。
4. ステップ4: 数値が0になるまでステップ2〜3を繰り返します。

C++での実装例

#include <iostream>
#include <math.h>
using namespace std;
void printSubNumbers(int n);
int main(){
    int n = 6789;
    cout<<"The number is "<<n<<" and the substring of number are :\n";
    printSubNumbers(n);
    return 0;
}
void printSubNumbers(int n){
    int s = log10(n);
    int d = (int)(pow(10, s) + 0.5);
    int k = d;
    while (n) {
        while (d) {
            cout<<(n / d)<<" ";
            d = d / 10;
        }
        n = n % k;
        k = k / 10;
        d = k;
    }
}

実行結果

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

The number is 6789 and the substring of number are :
6 67 678 6789 7 78 789 8 89 9

コードの解説

• log10(n) で数値の桁数を求め、pow(10, s) によって最大桁に対応する10のべき乗（4桁の数値なら1000）を取得します。+ 0.5 は浮動小数点誤差による丸め対策です。
• 内側の while ループでは、n / d を使って先頭からの桁並び（6、67、678、6789 など）を順番に出力します。
• n % k で最上位桁を除去し（6789 → 789）、外側のループで残りの桁に対して同じ処理を繰り返します。

計算量

• 時間計算量: O(d²)（d は数値の桁数）
• 空間計算量: O(1)

このように、除算・剰余・対数を活用すれば、文字列変換を一切使わずに数値のすべての部分文字列を効率的に出力できます。