Chúng ta được cung cấp một mảng các số nguyên dương. Mục đích là tìm các tập hợp con của các số trong một mảng sao cho mỗi tập hợp con có các số chẵn khác nhau trong đó. Tất cả các tập hợp có các phần tử giống nhau sẽ được tính là 1. [2,4,6] và [6,2,4] là cùng một tập hợp.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,3,5,7,8,3,2};
Đầu ra −Tổng số các tập hợp con có các số chẵn phân biệt là - 3
Giải thích - Các tập con sẽ là - [2], [8], [2,8]
Đầu vào - arr [] ={2,4,6};
Đầu ra −Tổng số các tập hợp con có các số chẵn phân biệt là - 7
Giải thích - Các tập con sẽ là - [2], [4], [6], [2,4], [2,6], [4,6], [2,4,6]
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi tạo một tập hợp tất cả các số chẵn trong mảng. Điều này cho phép đếm các số chẵn khác nhau. Công thức sẽ là 2 số chẵn - 1
-
Lấy một mảng số arr [].
-
Functionsubset_even (int arr [], int size) nhận một mảng số và trả về các tập hợp con có các số chẵn riêng biệt.
-
Lấy số lượng ban đầu là 0.
-
Tạo một
un_set cho các số chẵn. -
Traverse arr [] bằng vòng lặp for. Từ i =0 đến i
-
Nếu arr [i]% 2 ==0, nó là số chẵn. Chèn vào un_set.
-
Lấy count =un_set.size () // các số chẵn phân biệt.
-
Cập nhật count =pow (2, count) - 1.
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int subset_even(int arr[], int size){
int count = 0;
unordered_set<int> un_set;
for(int i=0; i<size; i++){
if (arr[i] % 2 == 0){
un_set.insert(arr[i]);
}
}
unordered_set<int>:: iterator i;
count = un_set.size();
count = pow(2, count) - 1;
return count;
}
int main(){
int arr[] = {10, 4, 21, 3, 5, 7, 6, 8};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subsets having distinct even numbers are: "<<subset_even(arr, size);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of subsets having distinct even numbers are: 15