Dada una array arr[] y un número K que está presente en la array al menos una vez, la tarea es encontrar la cantidad de subconjuntos en la array de modo que cada subconjunto contenga solo el valor K dado .
Ejemplos:
Entrada: arr[] = {1, 0, 0, 1, 0, 1, 2, 5, 2, 1}, K = 0
Salida: 4
Explicación:
De los dos 0 presentes en la array en el índice 2 y 3 , se pueden formar 3 subsecuencias: {0}, {0}, {0, 0}
Del 0 presente en el array en el índice 5, se puede formar 1 subsecuencia: {0}
Por lo tanto, se forman un total de 4 subsecuencias .
Entrada: arr[] = {1, 0, 0, 1, 1, 0, 0, 2, 3, 5}, K = 1
Salida: 4
Enfoque: para encontrar el número de subconjuntos , se debe hacer una observación sobre el número de subconjuntos formados para el número diferente de elementos en el conjunto dado.
Entonces, sea N el número de elementos para los cuales necesitamos encontrar los subconjuntos.
Entonces sí:
N = 1: Only one subset can be formed. N = 2: Three subsets can be formed. N = 3: Six subsets can be formed. N = 4: Ten subsets can be formed. . . . N = K: (K * (K + 1))/2 subsets can be formed.
Dado que estamos calculando el número de subconjuntos formados por la ocurrencia continua del valor K, la idea es encontrar el número de K continuos presentes en la array dada y encontrar el número usando la fórmula dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// number of subsets formed by
// the given value K
#include <iostream>
using namespace std;
// Function to find the number
// of subsets formed by the
// given value K
int count(int arr[], int N, int K)
{
// Count is used to maintain the
// number of continuous K's
int count = 0, ans = 0;
// Iterating through the array
for (int i = 0; i < N; i++) {
// If the element in the array
// is equal to K
if (arr[i] == K) {
count = count + 1;
}
else {
// count*(count+1)/2 is the
// total number of subsets
// with only K as their element
ans += (count * (count + 1)) / 2;
// Change count to 0 because
// other element apart from
// K has been found
count = 0;
}
}
// To handle the last set of K's
ans = ans + (count * (count + 1)) / 2;
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 0, 0, 1, 1, 0, 0 };
int N = sizeof(arr) / sizeof(int);
int K = 0;
cout << count(arr, N, K);
}
Java
// Java implementation to find the
// number of subsets formed by
// the given value K
class GFG{
// Function to find the number
// of subsets formed by the
// given value K
static int count(int arr[], int N, int K)
{
// Count is used to maintain the
// number of continuous K's
int count = 0, ans = 0;
// Iterating through the array
for (int i = 0; i < N; i++) {
// If the element in the array
// is equal to K
if (arr[i] == K) {
count = count + 1;
}
else {
// count*(count+1)/2 is the
// total number of subsets
// with only K as their element
ans += (count * (count + 1)) / 2;
// Change count to 0 because
// other element apart from
// K has been found
count = 0;
}
}
// To handle the last set of K's
ans = ans + (count * (count + 1)) / 2;
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 0, 0, 1, 1, 0, 0 };
int N = arr.length;
int K = 0;
System.out.print(count(arr, N, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation to find the # number of subsets formed by # the given value K # Function to find the number # of subsets formed by the # given value K def count(arr, N, K): # Count is used to maintain the # number of continuous K's count = 0 ans = 0 # Iterating through the array for i in range(N): # If the element in the array # is equal to K if (arr[i] == K): count = count + 1 else: # count*(count+1)/2 is the # total number of subsets # with only K as their element ans += (count * (count + 1)) // 2 # Change count to 0 because # other element apart from # K has been found count = 0 # To handle the last set of K's ans = ans + (count * (count + 1)) // 2 return ans # Driver code if __name__ == '__main__': arr = [1, 0, 0, 1, 1, 0, 0] N = len(arr) K = 0 print(count(arr, N, K)) # This code is contributed by Surendra_Gangwar
C#
// C# implementation to find the
// number of subsets formed by
// the given value K
using System;
class GFG{
// Function to find the number
// of subsets formed by the
// given value K
static int count(int []arr, int N, int K)
{
// Count is used to maintain the
// number of continuous K's
int count = 0, ans = 0;
// Iterating through the array
for(int i = 0; i < N; i++)
{
// If the element in the array
// is equal to K
if (arr[i] == K)
{
count = count + 1;
}
else
{
// count*(count+1)/2 is the
// total number of subsets
// with only K as their element
ans += (count * (count + 1)) / 2;
// Change count to 0 because
// other element apart from
// K has been found
count = 0;
}
}
// To handle the last set of K's
ans = ans + (count * (count + 1)) / 2;
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 0, 0, 1, 1, 0, 0 };
int N = arr.Length;
int K = 0;
Console.Write(count(arr, N, K));
}
}
//This is contributed by shivanisinghss2110
Javascript
<script>
// Javascript implementation to find the
// number of subsets formed by
// the given value K
// Function to find the number
// of subsets formed by the
// given value K
function count(arr, N, K)
{
// Count is used to maintain the
// number of continuous K's
let count = 0, ans = 0;
// Iterating through the array
for (let i = 0; i < N; i++)
{
// If the element in the array
// is equal to K
if (arr[i] == K) {
count = count + 1;
}
else {
// count*(count+1)/2 is the
// total number of subsets
// with only K as their element
ans += (count * (count + 1)) / 2;
// Change count to 0 because
// other element apart from
// K has been found
count = 0;
}
}
// To handle the last set of K's
ans = ans + (count * (count + 1)) / 2;
return ans;
}
let arr = [ 1, 0, 0, 1, 1, 0, 0 ];
let N = arr.length;
let K = 0;
document.write(count(arr, N, K));
//his code is contributed by divyeshrabadiya
</script>
6
Complejidad de tiempo: O(N) , donde N es el tamaño de la array.