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 Falseif __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");} |
Output
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 groupsvoid checkPartition(int N, int K){ // Invalid case if (N < (K * (K + 1)) / 2) { cout << "No"; } else { cout << "Yes"; }}// Driver codeint 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 groupsvoid checkPartition(int N, int K){ // Invalid case if (N < (K * (K + 1)) / 2) { printf("No"); } else { printf("Yes"); }}// Driver codeint main(){ int N = 6, K = 5; checkPartition(N, K); return 0;} |
Java
// Java code to implement above approachimport 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 approachdef checkPartition(N, K): # Invalid case if (N < (K*(K + 1))//2): print("No") else: print("Yes")# Driver codeif __name__ == '__main__': N = 6 K = 5 checkPartition(N, K) |
C#
// C# code to implement above approachusing 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> |
Output
No
Time Complexity: O(1)
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!
