削除操作後に配列の縮小サイズを見つけるC++プログラム

n個の要素を持つ配列Aがあるとします。 n個の正の整数を持つパスワードがあると考えてください。配列に次の操作を適用します。操作は、互いに同じではない2つの隣接する要素を削除し、それらの合計をその場所に配置することです。したがって、この操作により、配列のサイズが1つ小さくなります。これらの操作を実行した後、配列の可能な限り短い長さを見つける必要があります。

したがって、入力がA =[2、1、3、1]の場合、出力は1になります。これは、（1、3）を選択すると、配列が[2、4、1]になるため、 （2、4）を使用して配列[6、1]を作成し、最後の2つを選択して[7]を取得します。

ステップ

これを解決するには、次の手順に従います-

n := size of A
Define one set se
for initialize i := 0, when i < n, update (increase i by 1), do:
   insert A[i] into se
if size of se is same as 1, then:
   return n
Otherwise
   return 1

例

理解を深めるために、次の実装を見てみましょう-

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

int solve(vector<int> A) {
   int n = A.size();
   set<int> a;
   for (int i = 0; i < n; i++) {
      a.insert(A[i]);
   }
   if (a.size() == 1)
      return n;
   else
      return 1;
}
int main() {
   vector<int> A = { 2, 1, 3, 1 };
   cout << solve(A) << endl;
}

入力

{ 2, 1, 3, 1 }

出力

1