Given an array, arr[] of size N and an integer K, the task is to split the array into K non-intersecting subsets such that union of all the K subsets is equal to the given array.
Examples:
Input : arr[]= {2, 3}, K=2
Output: 4
Explanations:
Possible ways to partition the array into K(=2) subsets are:{ {{}, {2, 3}}, {{2}, {3}}, {{3}, {2}}, {{2, 3}, {}} }.
Therefore, the required output is 4.Input: arr[] = {2, 2, 3, 3}, K = 3
Output: 9
Approach: The problem can be solved based on the following observations:
The total number of ways to place an element into any one of the K subsets = K.
Therefore, the total number of ways to place all distinct elements of the given array into K subsets = K × K × …..× K(M times) = KM
Where M = total number of distinct elements in the given array.
Follow the steps below to solve the problem:
- Count distinct elements, say M present in the given array.
- Print the value of power(K, M).
Below is the implementation of the above approach:
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 conditionint 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 Codeint 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 conditionstatic 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 Codepublic 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 conditiondef 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 Codeif __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 conditionstatic 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 codepublic 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 conditionfunction 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 Codevar arr = [ 2, 3 ];var N = arr.length;var K = 2;document.write( cntWays(arr, N, K));</script> |
Output:
4
Time Complexity: O(log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
