C++で九九表のK番目に小さい数を二分探索で効率的に求める方法

掛け算の九九表は誰もが知っていますが、その中からk番目に小さい数を素早く見つけられるでしょうか。本記事では、高さm・幅nのm×nの九九表と正整数kが与えられたとき、表の中でk番目に小さい数を求めるアルゴリズムをC++で解説します。

問題の例

例えば、m = 3、n = 3、k = 6の場合、出力は4となります。このときの九九表は以下の通りです。

表の要素を昇順に並べると [1, 2, 2, 3, 3, 4, 6, 6, 9] となるため、6番目に小さい要素は4であることが分かります。

解法のアプローチ:二分探索

この問題は二分探索を使うことで効率的に解けます。まず、補助関数ok(m, n, x)を定義します。この関数は、九九表の中でx以下の値がいくつ存在するかを数えて返します。

• ret := 0 と初期化する
• i を1からnまで1ずつ増やしながら、以下を繰り返す
  • temp := min(x / i, m)
  • ret := ret + temp
• ret を返す

各行iには、iの倍数のうちx以下の数が min(x / i, m) 個含まれるため、これを全行について合計すれば、x以下の値の総数が求まります。

続いて、メイン処理では以下の手順で二分探索を行います。

• ret := -1、low := 1、high := m × n と初期化する
• low ≤ high の間、以下を繰り返す
  • mid := low + (high − low) / 2
  • cnt := ok(m, n, mid)
  • cnt ≥ k の場合:high := mid − 1、ret := mid
  • それ以外の場合:low := mid + 1
• ret を返す

「x以下の数がk個以上存在するような最小のx」を二分探索で絞り込むことで、k番目に小さい数を正確に特定できます。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int ok(int m, int n, int x){
        int ret = 0;
        for(int i = 1; i <= n; i++){
            int temp = min(x / i, m);
            ret += temp;
        }
        return ret;
    }
    int findKthNumber(int m, int n, int k) {
        int ret = -1;
        int low = 1;
        int high = m * n ;
        while(low <= high){
            int mid = low + (high - low)/ 2;
            int cnt = ok(m, n, mid);
            if(cnt >= k){
                high = mid - 1;
                ret = mid;
            }else low = mid + 1;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.findKthNumber(3,3,6));
}

入力と出力

入力:m = 3、n = 3、k = 6(findKthNumber(3, 3, 6)を呼び出し)

出力:

4

このように、二分探索とカウント用の補助関数を組み合わせることで、大きな九九表でも高速にk番目に小さい数を求められます。