Chương trình C ++ để tìm kích thước giảm của mảng sau khi thực hiện các thao tác xóa

Giả sử chúng ta có một mảng A với n phần tử. Hãy xem xét có một mật khẩu với n số nguyên dương. Chúng tôi áp dụng các hoạt động sau trên mảng. Các phép toán là loại bỏ hai phần tử liền kề không giống nhau, sau đó đặt tổng của chúng tại vị trí đó. Vì vậy, thao tác này sẽ làm giảm kích thước của mảng đi 1. Chúng ta phải tìm độ dài ngắn nhất có thể có của mảng sau khi thực hiện các thao tác này.

Vì vậy, nếu đầu vào là A =[2, 1, 3, 1], thì đầu ra sẽ là 1, vì nếu chúng ta chọn (1, 3), mảng sẽ là [2, 4, 1], sau đó chọn (2, 4) để tạo mảng [6, 1], sau đó chọn hai phần cuối cùng để lấy [7].

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

{ 2, 1, 3, 1 }

Đầu ra

1