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: 3
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>
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