C++で指定された条件を満たすサブセットをカウントします

数値の配列と整数xを入力として指定します。目標は、arr []のすべてのサブセットを見つけて、そのセットの個々の要素とそれらの合計をxで完全に割り切れるようにすることです。

例

入力

arr[] = {1,2,3,4,5,6} x=3

出力

Count of subsets that satisfy the given condition :3

説明

The subsets will be:
[3], [6], [3,6]

入力

arr[] = {1,2,3,4,5,6} x=4

出力

Count of subsets that satisfy the given condition :1

説明

The subsets will be:
[4]

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、xで完全に割り切れるarr []の要素をカウントしてから、2 ^count を返します。 必要なサブセット数として-1。

• 整数配列arr[]を取ります。

• xを入力として使用します。

• 関数count（int arr []、int n、int x）は、配列とxを受け取り、指定された条件を満たすサブセットの数を返します。

• xが1の場合、すべての要素が分割されるため、return

例

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int sub_sets(int arr[], int size, int val){
int count = 0;
if (val == 1){
   count = pow(2, size) − 1;
      return count;
   }
   for (int i = 0; i < size; i++){
      if (arr[i] % val == 0){
         count++;
      }
   }
   count = pow(2, count) − 1;
   return count;
}
int main(){
   int arr[] = { 4, 6, 1, 3, 8, 10, 12 }, val = 4;
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of sub−sets that satisfy the given condition are: "<<sub_sets(arr, size, val);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of sub−sets that satisfy the given condition are: 7