C++で指定した操作を用いて配列を単一の要素へ縮小する方法

整数変数 Number が入力として与えられます。ここでは、1 から Number までの範囲の要素が昇順に並んだ配列を考えます。この配列に対して「各ステップで奇数番目の位置にある要素を削除する」という操作を繰り返し、要素が 1 つだけ残るまで処理を行います。そして、最後に残ったその要素を出力することがゴールです。

注意： 要素の位置は、配列のインデックス 0 を「1 番目」、インデックス 1 を「2 番目」として数えるものとします。

配列の要素数ごとのテストケース

入力 Number=1 → 出力 = 1

入力 Number=2 → 出力 = 2

入力 Number=3 → 出力 = 2

入力 Number=4 → 出力 = 4

入力 Number=5 → 出力 = 4

入力 Number=6 → 出力 = 4

入力 Number=7 → 出力 = 4

……

入力 Number=12 → 出力 = 8

入力 Number=20 → 出力 = 16

上記の結果から、2ⁱ ～ 2ⁱ⁺¹-1 の範囲の数値に対しては、出力が必ず 2ⁱ になるという規則性が見て取れます。

具体例

入力 − Number=7

出力 − 縮小操作後に残る単一の要素：4

説明 − 先頭の要素は 1 番目の位置にあり、以降も同様に数えます。

初期の配列は [ 1 2 3 4 5 6 7 ]

1 回目の操作後：[ 2 4 6 ]

2 回目の操作後：[ 4 ]

入力 − Number=18

出力 − 縮小操作後に残る単一の要素：16

説明 − 先頭の要素は 1 番目の位置にあり、以降も同様に数えます。

初期の配列は [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ]

1 回目の操作後：[ 2 4 6 8 10 12 14 16 18 ]

2 回目の操作後：[ 2 8 12 16 ]

3 回目の操作後：[ 8 16 ]

4 回目の操作後：[ 16 ]

プログラムで使用しているアプローチ

このアプローチでは、上記の規則性（公式）に基づいて while ループを使いながら最終結果を計算します。初期値を 2 とし、「result × 2 ≤ 入力値」が成立する間、各反復処理で値を 2 倍していきます。

• 入力変数 Number を受け取ります。

• 関数 getsingleElement(long num) が入力値を受け取り、上記の公式に基づいた結果を出力します。

• 結果を格納する変数 result を用意します。

• result を 2 で初期化します。

• while ループで「result × 2 ≤ num」が満たされる間、処理を繰り返します。

• ループ内で result を 2 倍にします。

• ループが終了した時点で、目的の値が得られています。

• result を返却します。

• main 関数内で結果を出力します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
long getsingleElement(long num){
   long result;
   result=2;
   while(result*2 <= num){
      result=result*2;
   }
   return result;
}
int main(){
   int Number = 20;
   cout<<"The single element after reduction operation is : "<<getsingleElement(Number) ;
   return 0;
}

出力

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

The single element after reduction operation is : 16