Dada una array , arr[] de tamaño N y un número entero K , la tarea es dividir la array en K subconjuntos que no se intersecan, de modo que la unión de todos los K subconjuntos sea igual a la array dada.
Ejemplos:
Entrada: arr[]= {2, 3}, K=2
Salida: 4
Explicaciones:
Las formas posibles de dividir la array en K(=2) subconjuntos son:{ {{}, {2, 3}}, {{2 }, {3}}, {{3}, {2}}, {{2, 3}, {}} }.
Por lo tanto, la salida requerida es 4.Entrada: arr[] = {2, 2, 3, 3}, K = 3
Salida : 9
Enfoque : El problema se puede resolver en base a las siguientes observaciones:
El número total de formas de colocar un elemento en cualquiera de los K subconjuntos = K.
Por lo tanto, el número total de formas de colocar todos los elementos distintos de la array dada en K subconjuntos = K × K × …..× K(M veces) = K M
Donde M = número total de elementos distintos en la array dada.
Siga los pasos a continuación para resolver el problema:
- Cuente elementos distintos , digamos M presentes en la array dada.
- Imprime el valor de power(K, M) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to get
// the value of pow(K, M)
int power(int K, int M)
{
// Stores value of pow(K, M)
int res = 1;
// Calculate value of pow(K, N)
while (M > 0) {
// If N is odd, update
// res
if ((M & 1) == 1) {
res = (res * K);
}
// Update M to M / 2
M = M >> 1;
// Update K
K = (K * K);
}
return res;
}
// Function to print total ways
// to split the array that
// satisfies the given condition
int cntWays(int arr[], int N,
int K)
{
// Stores total ways that
// satisfies the given
// condition
int cntways = 0;
// Stores count of distinct
// elements in the given arr
int M = 0;
// Store distinct elements
// of the given array
unordered_set<int> st;
// Traverse the given array
for (int i = 0; i < N; i++) {
// Insert current element
// into set st.
st.insert(arr[i]);
}
// Update M
M = st.size();
// Update cntways
cntways = power(K, M);
return cntways;
}
// Driver Code
int main()
{
int arr[] = { 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << cntWays(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to get
// the value of pow(K, M)
static int power(int K, int M)
{
// Stores value of pow(K, M)
int res = 1;
// Calculate value of pow(K, N)
while (M > 0)
{
// If N is odd, update
// res
if ((M & 1) == 1)
{
res = (res * K);
}
// Update M to M / 2
M = M >> 1;
// Update K
K = (K * K);
}
return res;
}
// Function to print total ways
// to split the array that
// satisfies the given condition
static int cntWays(int arr[], int N,
int K)
{
// Stores total ways that
// satisfies the given
// condition
int cntways = 0;
// Stores count of distinct
// elements in the given arr
int M = 0;
// Store distinct elements
// of the given array
Set<Integer> st = new HashSet<Integer>();
// Traverse the given array
for(int i = 0; i < N; i++)
{
// Insert current element
// into set st.
st.add(arr[i]);
}
// Update M
M = st.size();
// Update cntways
cntways = power(K, M);
return cntways;
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 2, 3 };
int N = arr.length;
int K = 2;
System.out.println(cntWays(arr, N, K));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach # Function to get # the value of pow(K, M) def power(K, M): # Stores value of pow(K, M) res = 1 # Calculate value of pow(K, N) while (M > 0): # If N is odd, update # res if ((M & 1) == 1): res = (res * K) # Update M to M / 2 M = M >> 1 # Update K K = (K * K) return res # Function to print total ways # to split the array that # satisfies the given condition def cntWays(arr, N, K): # Stores total ways that # satisfies the given # condition cntways = 0 # Stores count of distinct # elements in the given arr M = 0 # Store distinct elements # of the given array st = set() # Traverse the given array for i in range(N): # Insert current element # into set st. st.add(arr[i]) # Update M M = len(st) # Update cntways cntways = power(K, M) return cntways # Driver Code if __name__ == '__main__': arr = [ 2, 3 ] N = len(arr) K = 2 print(cntWays(arr, N, K)) # This code is contributed by math_lover
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to get
// the value of pow(K, M)
static int power(int K, int M)
{
// Stores value of pow(K, M)
int res = 1;
// Calculate value of pow(K, N)
while (M > 0)
{
// If N is odd, update
// res
if ((M & 1) == 1)
{
res = (res * K);
}
// Update M to M / 2
M = M >> 1;
// Update K
K = (K * K);
}
return res;
}
// Function to print total ways
// to split the array that
// satisfies the given condition
static int cntWays(int[] arr, int N,
int K)
{
// Stores total ways that
// satisfies the given
// condition
int cntways = 0;
// Stores count of distinct
// elements in the given arr
int M = 0;
// Store distinct elements
// of the given array
HashSet<int> st = new HashSet<int>();
// Traverse the given array
for(int i = 0; i < N; i++)
{
// Insert current element
// into set st.
st.Add(arr[i]);
}
// Update M
M = st.Count;
// Update cntways
cntways = power(K, M);
return cntways;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3 };
int N = arr.Length;
int K = 2;
Console.WriteLine(cntWays(arr, N, K));
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to get
// the value of pow(K, M)
function power(K, M)
{
// Stores value of pow(K, M)
var res = 1;
// Calculate value of pow(K, N)
while (M > 0) {
// If N is odd, update
// res
if ((M & 1) == 1) {
res = (res * K);
}
// Update M to M / 2
M = M >> 1;
// Update K
K = (K * K);
}
return res;
}
// Function to print total ways
// to split the array that
// satisfies the given condition
function cntWays( arr, N, K)
{
// Stores total ways that
// satisfies the given
// condition
var cntways = 0;
// Stores count of distinct
// elements in the given arr
var M = 0;
// Store distinct elements
// of the given array
var st = new Set();
// Traverse the given array
for (var i = 0; i < N; i++) {
// Insert current element
// into set st.
st.add(arr[i]);
}
// Update M
M = st.size;
// Update cntways
cntways = power(K, M);
return cntways;
}
// Driver Code
var arr = [ 2, 3 ];
var N = arr.length;
var K = 2;
document.write( cntWays(arr, N, K));
</script>
Producción:
4
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)