Given N balls. For convenience, we denote the color of each ball as — lowercase letters. We have to distribute N balls among K people. They will be upset if they get two balls of the same color. We can give any number of balls to people and they won’t be upset even if they do not get any balls, but, we have to distribute all the balls, such that no one will be upset — print YES, if it is possible, and NO, otherwise.
Examples:
Input : 4 2 // value of N and K
aabb // colors of given balls
Output : YES
We can give 1st and 3rd ball to the first person,
and 2nd and 4th to the second.
Input : 6 3 // value of N and K
aacaab // colors of given balls
Output : NO
We need to give all balls of color a, but one
ball will stay, that's why answer is NO
The approach will be really simple. We will create a count array to keep the count of each color that occurs and then we will check if any color occurs more than the number of people we have. If it occurs, we will print NO else YES.
The implementation of the above idea is given below.
C++
// CPP program to find if its possible to // distribute balls without repetition #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 26; // function to find if its possible to // distribute balls or not bool distributingBalls(int k, int n, string str) { // count array to count how many times // each color has occurred int a[MAX_CHAR] = {0}; for (int i = 0; i < n; i++){ // increasing count of each color // every time it appears a[str[i] - 'a']++; } for (int i = 0; i < MAX_CHAR; i++) // to check if any color appears // more than K times if it does // we will print NO if (a[i] > k) return false; return true; } // Driver code int main() { long long int n = 6, k = 3; string str = "aacaab"; if (distributingBalls(k, n, str)) cout << "YES"; else cout << "NO"; return 0; } |
Java
// Java program to find if its possible // to distribute balls without repetition import java.io.*; public class GFG { static int MAX_CHAR = 26; // function to find if its possible // to distribute balls or not static boolean distributingBalls(long k, long n, String str) { // count array to count how many // times each color has occurred int []a = new int[MAX_CHAR]; for (int i = 0; i < n; i++) { // increasing count of each // color every time it appears a[str.charAt(i) - 'a']++; } for (int i = 0; i < MAX_CHAR; i++) // to check if any color appears // more than K times if it does // we will print NO if (a[i] > k) return false; return true; } // Driver code static public void main (String[] args) { long n = 6, k = 3; String str = "aacaab"; if (distributingBalls(k, n, str)) System.out.println("YES"); else System.out.println("NO"); } } // This code is contributed by vt_m. |
Python3
# Python3 program to find if its possible to # distribute balls without repetition MAX_CHAR = 26 # function to find if its possible to # distribute balls or not def distributingBalls(k, n, string) : # count array to count how many times # each color has occurred a = [0] * MAX_CHAR for i in range(n) : # increasing count of each color # every time it appears a[ord(string[i]) - ord('a')] += 1 for i in range(MAX_CHAR) : # to check if any color appears # more than K times if it does # we will print NO if (a[i] > k) : return False return True # Driver code if __name__ == "__main__" : n, k = 6, 3 string = "aacaab" if (distributingBalls(k, n, string)) : print("YES") else : print("NO") # This code is contributed by Ryuga |
C#
// C# program to find if its possible to // distribute balls without repetition using System; public class GFG { static int MAX_CHAR = 26; // function to find if its possible // to distribute balls or not static bool distributingBalls(long k, long n, string str) { // count array to count how many // times each color has occurred int []a = new int[MAX_CHAR]; for (int i = 0; i < n; i++) { // increasing count of each // color every time it appears a[str[i] - 'a']++; } for (int i = 0; i < MAX_CHAR; i++) // to check if any color // appears more than K // times if it does we // will print NO if (a[i] > k) return false; return true; } // Driver code static public void Main () { long n = 6, k = 3; string str = "aacaab"; if (distributingBalls(k, n, str)) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript program to find if its possible to // distribute balls without repetition let MAX_CHAR = 26; // function to find if its possible // to distribute balls or not function distributingBalls(k, n, str) { // count array to count how many // times each color has occurred let a = new Array(MAX_CHAR); a.fill(0); for (let i = 0; i < n; i++) { // increasing count of each // color every time it appears a[str[i].charCodeAt() - 'a'.charCodeAt()]++; } for (let i = 0; i < MAX_CHAR; i++) // to check if any color // appears more than K // times if it does we // will print NO if (a[i] > k) return false; return true; } let n = 6, k = 3; let str = "aacaab"; if (distributingBalls(k, n, str)) document.write("YES"); else document.write("NO"); </script> |
Output
NO
Time complexity : O(n)
Auxiliary Space : O(1)
This article is contributed by Sarthak Kohli. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
