Check whether N items can be divided into K groups of unique size
Given integers N and K, the task is to check if it is possible to divide N numbers into K groups such that all the K groups are of different size and each part has at least one number.
Examples:
Input: N = 5, K = 2
Output: Yes
Explanation: 5 numbers can be divided into 2 parts of different size. The possible size of the groups can be (1, 4) and (2, 3).Input: N = 3, K = 3
Output: No
Explanation: 3 numbers cannot be divide into 3 groups of unique size.
Approach:
- Define a function canPartition that takes four arguments: N (the total number of items to be partitioned), K (the number of groups to partition into), curr (the current item being considered for partitioning), and num_groups (the current number of groups formed so far).
- The base case for the recursive function is when N is 0 and num_groups is equal to K. This means that a valid partition has been found and the function should return true.
- Another base case is when N is negative, curr is greater than N, or num_groups is greater than or equal to K. This means that the current partition is invalid and the function should return false.
- Iterate over the range from curr to N (inclusive) and for each value i, recursively call canPartition with N-i as the new N value, K as the same, i+1 as the new curr value, and num_groups+1 as the new num_groups value.
- If the recursive call returns true, this means that a valid partition has been found and the function should return true.
- If all possible partitions have been checked and none of them are valid, the function should backtrack and try a different group size by returning false.
C++
#include <bits/stdc++.h> using namespace std; bool canPartition( int N, int K, int curr, int num_groups) { if (N == 0 && num_groups == K) { // Found a valid partition return true ; } if (N < 0 || curr > N || num_groups >= K) { // Invalid partition return false ; } for ( int i = curr; i <= N; i++) { if (canPartition(N-i, K, i+1, num_groups+1)) { return true ; } } // Backtrack and try a different group size return false ; } int main() { int N = 6, K = 5; if (canPartition(N, K, 1, 0)) { cout << "Yes" ; } else { cout << "No" ; } return 0; } |
Java
import java.util.*; public class Main { public static void main(String[] args) { int N = 6 , K = 5 ; if (canPartition(N, K, 1 , 0 )) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } public static boolean canPartition( int N, int K, int curr, int num_groups) { if (N == 0 && num_groups == K) { // Found a valid partition return true ; } if (N < 0 || curr > N || num_groups >= K) { // Invalid partition return false ; } for ( int i = curr; i <= N; i++) { if (canPartition(N - i, K, i + 1 , num_groups + 1 )) { return true ; } } // Backtrack and try a different group size return false ; } } |
Python
def can_partition(N, K, curr, num_groups): if N = = 0 and num_groups = = K: # Found a valid partition return True if N < 0 or curr > N or num_groups > = K: # Invalid partition return False for i in range (curr, N + 1 ): if can_partition(N - i, K, i + 1 , num_groups + 1 ): return True # Backtrack and try a different group size return False if __name__ = = '__main__' : N = 6 K = 5 if can_partition(N, K, 1 , 0 ): print ( "Yes" ) else : print ( "No" ) |
C#
using System; class GFG { // Function to check if N can be partitioned into K groups static bool CanPartition( int N, int K, int curr, int numGroups) { if (N == 0 && numGroups == K) { // Found a valid partition return true ; } if (N < 0 || curr > N || numGroups >= K) { // Invalid partition return false ; } for ( int i = curr; i <= N; i++) { if (CanPartition(N - i, K, i + 1, numGroups + 1)) { return true ; } } // Backtrack and try a different group size return false ; } static void Main() { int N = 6, K = 5; if (CanPartition(N, K, 1, 0)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
function canPartition(N, K, curr, num_groups) { if (N === 0 && num_groups === K) { // Found a valid partition return true ; } if (N < 0 || curr > N || num_groups >= K) { // Invalid partition return false ; } for (let i = curr; i <= N; i++) { if (canPartition(N - i, K, i + 1, num_groups + 1)) { return true ; } } // Backtrack and try a different group size return false ; } const N = 6; const K = 5; if (canPartition(N, K, 1, 0)) { console.log( "Yes" ); } else { console.log( "No" ); } |
No
Time Complexity: O(2^N), where N is the input integer N. This is because the algorithm tries all possible combinations of partitions, and there can be up to 2^N different combinations.
Space Complexity: O(K), where K is the number of groups. This is because at any point during the recursion, there will be at most K recursive calls on the call stack, corresponding to the K groups being formed. Each call takes up constant space, so the overall space complexity is O(K).
Approach: The problem can be solved on the basis of following observation.
To divide N numbers into K groups such that each group has at least one number and no two groups have same size:
- There should be at least K numbers. If N < K, then division is not possible.
- If N > K then the K groups will be at least of size 1, 2, 3, 4 . . . K . So N must be at least K*(K + 1)/2.
Therefore, the condition to be satisfied is N ≥ K*(K + 1)/2.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible // to break N in K groups void checkPartition( int N, int K) { // Invalid case if (N < (K * (K + 1)) / 2) { cout << "No" ; } else { cout << "Yes" ; } } // Driver code int main() { int N = 6, K = 5; checkPartition(N, K); return 0; } |
C
// C code to implement above approach #include <stdio.h> // Function to check if it is possible // to break N in K groups void checkPartition( int N, int K) { // Invalid case if (N < (K * (K + 1)) / 2) { printf ( "No" ); } else { printf ( "Yes" ); } } // Driver code int main() { int N = 6, K = 5; checkPartition(N, K); return 0; } |
Java
// Java code to implement above approach import java.io.*; class GFG { // Function to check if it is possible // to break N in K groups public static void checkPartition( int N, int K) { // Invalid case if (N < (K * (K + 1 ) / 2 )) { System.out.print( "No" ); } else { System.out.print( "Yes" ); } } // Driver code public static void main(String[] args) { int N = 6 , K = 5 ; checkPartition(N, K); } } |
Python3
# Python code to implement above approach def checkPartition(N, K): # Invalid case if (N < (K * (K + 1 )) / / 2 ): print ( "No" ) else : print ( "Yes" ) # Driver code if __name__ = = '__main__' : N = 6 K = 5 checkPartition(N, K) |
C#
// C# code to implement above approach using System; class GFG { // Function to check if it is possible // to break N in K groups public static void checkPartition( int N, int K) { // Invalid case if (N < (K * (K + 1) / 2)) { Console.Write( "No" ); } else { Console.Write( "Yes" ); } } // Driver code public static void Main() { int N = 6, K = 5; checkPartition(N, K); } } // This code is contributed by saurabh_jaiswal. |
Javascript
<script> // JavaScript code for the above approach // Function to check if it is possible // to break N in K groups function checkPartition(N, K) { // Invalid case if (N < Math.floor((K * (K + 1)) / 2)) { document.write( "No" ); } else { document.write( "Yes" ); } } // Driver code let N = 6, K = 5; checkPartition(N, K); // This code is contributed by Potta Lokesh </script> |
No
Time Complexity: O(1)
Auxiliary Space: O(1).