Contar subconjuntos que satisfacen la condición dada

Dada una array arr[] y un entero x , la tarea es contar el número de subconjuntos de arr[] suma de todos cuyos subconjuntos (individualmente) es divisible por x .
Ejemplos: 
 

Entrada: arr[] = {2, 4, 3, 7}, x = 2 
Salida:
Todos los subconjuntos válidos son {2}, {4} y {2, 4} 
{2} => 2 es divisible por 2 
{4} => 4 es divisible por 2 
{2, 4} => 2, 4 y 6 son todos divisibles por 2
Entrada: arr[] = {2, 3, 4, 5}, x = 1 
Salida: 15 
 

Enfoque: Para elegir una suma de subconjuntos de todos cuyos subconjuntos sea divisible por x , todos los elementos del subconjunto deben ser divisibles por x . Asi que, 
 

  • Cuente todos los elementos de la array que es divisible por x y almacénelos en una variable count .
  • Ahora, todos los subconjuntos posibles que satisfagan la condición serán 2 recuentos – 1

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to return the count of the required sub-sets
ll count(int arr[], int n, int x)
{
 
    // Every element is divisible by 1
    if (x == 1) {
        ll ans = pow(2, n) - 1;
        return ans;
    }
 
    // Count of elements which are divisible by x
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % x == 0)
            count++;
    }
 
    ll ans = pow(2, count) - 1;
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 1;
    cout << count(arr, n, x) << endl;
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class solution
{
 
// Function to return the count of the required sub-sets
static long count(int arr[], int n, int x)
{
 
    // Every element is divisible by 1
    if (x == 1) {
        long ans = (long)Math.pow(2, n) - 1;
        return ans;
    }
 
    // Count of elements which are divisible by x
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % x == 0)
            count++;
    }
 
    long ans = (long)Math.pow(2, count) - 1;
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int []arr = { 2, 4, 3, 5 };
    int n = arr.length;
    int x = 1;
    System.out.println(count(arr, n, x));
}
}

Python3

# Python3 implementation of the approach
 
# Function to return the count of
# the required sub-sets
def count(arr, n, x) :
 
    # Every element is divisible by 1
    if (x == 1) :
        ans = pow(2, n) - 1
        return ans;
     
    # Count of elements which are
    # divisible by x
    count = 0
    for i in range(n) :
        if (arr[i] % x == 0) :
            count += 1
 
    ans = pow(2, count) - 1
    return ans
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 2, 4, 3, 5 ]
    n = len(arr)
    x = 1
    print(count(arr, n, x))
 
# This code is contributed by Ryuga

C#

//C# implementation of the approach
 
using System;
 
public class GFG{
     
// Function to return the count of the required sub-sets
static double count(int []arr, int n, int x)
{
    double ans=0;
    // Every element is divisible by 1
    if (x == 1) {
        ans = (Math.Pow(2, n) - 1);
        return ans;
    }
 
    // Count of elements which are divisible by x
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % x == 0)
            count++;
    }
 
    ans = (Math.Pow(2, count) - 1);
    return ans;
}
 
// Driver code
     
    static public void Main (){
     
    int []arr = { 2, 4, 3, 5 };
    int n = arr.Length;
    int x = 1;
    Console.WriteLine(count(arr, n, x));
    }
}

PHP

<?php
// PHP  implementation of the approach
 
// Function to return the count of the required sub-sets
function count_t($arr, $n, $x)
{
    // Every element is divisible by 1
    if ($x == 1) {
    $ans = pow(2, $n) - 1;
        return $ans;
    }
 
    // Count of elements which are divisible by x
    $count = 0;
    for ($i = 0; $i < $n; $i++) {
        if ($arr[$i] % $x == 0)
            $count++;
    }
 
    $ans = pow(2, $count) - 1;
    return $ans;
}
 
// Driver code
 
    $arr = array( 2, 4, 3, 5 );
    $n = sizeof($arr) / sizeof($arr[0]);
    $x = 1;
    echo  count_t($arr, $n, $x);
     
#This code is contributed by akt_mit
?>

Javascript

<script>
 
    // Javascript implementation of the approach
     
    // Function to return the count of
    // the required sub-sets
    function count(arr, n, x)
    {
        let ans=0;
        // Every element is divisible by 1
        if (x == 1) {
            ans = (Math.pow(2, n) - 1);
            return ans;
        }
 
        // Count of elements which are divisible by x
        let count = 0;
        for (let i = 0; i < n; i++) {
            if (arr[i] % x == 0)
                count++;
        }
 
        ans = (Math.pow(2, count) - 1);
        return ans;
    }
     
    let arr = [ 2, 4, 3, 5 ];
    let n = arr.length;
    let x = 1;
    document.write(count(arr, n, x));
     
</script>
Producción: 

15

 

Publicación traducida automáticamente

Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *