【C++】奇数をすべて削除した範囲[1, n]におけるk番目に小さい数の求め方

問題の概要

この問題では、2つの整数 n と k が与えられます。求めるのは、範囲 [1, n] からすべての奇数を削除した状態で、k番目に小さい数を見つけることです。

つまり、偶数のみが残った範囲 [1, n] の中で、k番目に小さい値を特定する必要があります。

例えば、範囲 [1, 5] の場合、残る数は「2」と「4」になります。

具体例で理解しよう

• 入力： n = 12, k = 4
• 出力： 8

解説：

範囲 [1, n] に含まれる偶数は「2, 4, 6, 8, 10, 12」の6個です。この中で4番目に小さい要素は 8 となります。

解法のアプローチ

この解法は非常にシンプルです。n までの偶数の中から k 番目の要素を取り出すだけでよいため、次の式で簡単に計算できます。

k番目の要素 = 2 × k

ただし、この値が有効であるためには「2 × k ≤ n」を満たす必要があります。条件を満たさない場合、k番目に小さい偶数は範囲 [1, n] 内に存在しないことになります。

解法を実装したC++プログラム

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

int main() {

    int n = 124, k = 12;
    if(n >= 2 * k){
        cout<<"k番目に小さい数は "<<(2 * k);  
    }
    else
        cout<<"k番目に小さい数は見つかりません";
    return 0;
}

実行結果

k番目に小さい数は 24

まとめ

n = 124、k = 12 の場合は「2 × 12 = 24」となり、24 は範囲 [1, 124] 内に存在するため、答えは 24 です。この手法の計算量は O(1) と非常に効率的で、n がどれほど大きくても即座に答えを求めることができます。