C++で解く「9を含む整数の削除」問題:n進数変換の活用

問題の概要

整数 n が与えられたとき、次の操作を行った結果として得られる n 番目の整数を返します。まず 1 から始まる整数列を用意し、9 を含む整数(9、19、29 …)をすべて取り除きます。こうしてできる新しい整数列は、1、2、3、4、5、6、7、8、10、11 … となります。ここで、先頭の整数が 1 である点に注意してください。

たとえば、入力が 9 であれば出力は 10 になります。

解法の考え方

この問題は一見複雑そうですが、実は「9 を含まない整数列」の構造を利用すると、非常にエレガントに解くことができます。

9 を含まない正整数を順番に並べると、それは各桁が 0〜8 のみで構成された数、つまり9 進法で表した数と完全に一致します。したがって、「n 番目の整数」は単純にn を 9 進数に変換し、その各桁をそのまま 10 進数として読み直した値になります。

具体的な手順

• ret := 0(答えを格納する変数)

• s := 1(現在注目している桁の重み)

• n が 0 になるまで以下を繰り返します。

  • ret := ret + (n mod 9) × s

  • n := n ÷ 9(商で置き換える)

  • s := s × 10(次の桁へ進む)

計算例(n = 120 の場合)

120 ÷ 9 = 13 余り 3 → ret = 3
13 ÷ 9 = 1 余り 4 → ret = 43
1 ÷ 9 = 0 余り 1 → ret = 143

よって、答えは 143 となります。以下の実装を見ると理解がさらに深まるでしょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
   int newInteger(int n) {
      int ret = 0;
      lli s = 1;
      while (n) {
         ret += (n % 9) * s;
         n /= 9;
         s *= 10;
      }
      return ret;
   }
};

main() {
   Solution ob;
   cout << (ob.newInteger(120));
}

入力

120

出力

143

計算量

時間計算量は n を 9 で割り続ける回数に比例するため O(log₉ n)、空間計算量は O(1) です。なお、桁の重み s が大きくなるとオーバーフローの恐れがあるため、実装では long long 型を使用しています。