Given N sweets, which can be of many different types, and k customers, one customer won’t make the same type of sweet more than 2 pieces, the task is to find if it is possible to distribute all, then print “Yes” or otherwise “No”.
Given an array, arr[] represents an array of sweets. arr[i] is type of sweet.
Examples:
Input : arr[] = {1, 1, 2, 3, 1},
k = 2;
Output : Yes
There are three pieces of sweet type 1,
one piece of type 2 and one piece of
type 3. Two customers can distribute
sweets under given constraints.
Input : arr[] = {2, 3, 3, 5, 3, 3},
k = 2;
Output : Yes
Input : arr[] = {2, 3, 3, 5, 3, 3, 3},
k = 2;
Output : No
Method 1:
- Traverse array for each element.
- Count occurrences of each element in the array
- Check if the result of each element must be less than or equal to 2*k.
Implementation:
C++
// C++ program for above implementation#include <bits/stdc++.h>using namespace std;// Function to check occurrence of each elementbool checkCount(int arr[], int n, int k){ int count; // Start traversing the elements for (int i = 0; i < n; i++) { // Count occurrences of current element count = 0; for (int j = 0; j < n; j++) { if (arr[j] == arr[i]) count++; // If count of any element is greater // than 2*k then return false if (count > 2 * k) return false; } } return true;}// Drivers codeint main(){ int arr[] = { 1, 1, 2, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; checkCount(arr, n, k) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// java program for above implementationimport java.io.*;public class GFG { // Function to check occurrence of // each element static boolean checkCount(int []arr, int n, int k) { int count; // Start traversing the elements for (int i = 0; i < n; i++) { // Count occurrences of // current element count = 0; for (int j = 0; j < n; j++) { if (arr[j] == arr[i]) count++; // If count of any element // is greater than 2*k then // return false if (count > 2 * k) return false; } } return true; } // Drivers code static public void main (String[] args) { int []arr = { 1, 1, 2, 3, 1 }; int n = arr.length; int k = 2; if(checkCount(arr, n, k)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by vt_m. |
Python3
# Python 3 program for above implementation # Function to check occurrence # of each element def checkCount(arr, n, k): # Start traversing the elements for i in range(n): # Count occurrences of # current element count = 0 for j in range(n): if arr[j] == arr[i]: count += 1 # If count of any element is greater # than 2*k then return false if count > 2 * k: return False return True# Driver codearr = [1, 1, 2, 3, 1]n = len(arr)k = 2if checkCount(arr, n, k) == True: print("Yes")else: print("No")# This code is contributed by Shrikant13 |
C#
// C# program for above implementationusing System;public class GFG { // Function to check occurrence // of each element static bool checkCount(int []arr, int n, int k) { int count; // Start traversing the elements for (int i = 0; i < n; i++) { // Count occurrences of // current element count = 0; for (int j = 0; j < n; j++) { if (arr[j] == arr[i]) count++; // If count of any element // is greater than 2*k then // return false if (count > 2 * k) return false; } } return true; } // Drivers code static public void Main () { int []arr = { 1, 1, 2, 3, 1 }; int n = arr.Length; int k = 2; if(checkCount(arr, n, k)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program for above implementation// Function to check occurrence// of each elementfunction checkCount($arr, $n, $k){ $count; // Start traversing the elements for($i = 0; $i < $n; $i++) { // Count occurrences of // current element $count = 0; for($j = 0; $j < $n; $j++) { if ($arr[$j] == $arr[$i]) $count++; // If count of any element // is greater than 2*k then // return false if ($count > 2 * $k) return false; } } return true;} // Driver Code $arr = array(1, 1, 2, 3, 1); $n =count($arr); $k = 2; if(checkCount($arr, $n, $k)) echo "Yes"; else echo "No";// This code is contributed by anuj_67.?> |
Javascript
<script> // Javascript program for above implementation // Function to check occurrence // of each element function checkCount(arr, n, k) { let count; // Start traversing the elements for (let i = 0; i < n; i++) { // Count occurrences of // current element count = 0; for (let j = 0; j < n; j++) { if (arr[j] == arr[i]) count++; // If count of any element // is greater than 2*k then // return false if (count > 2 * k) return false; } } return true; } let arr = [ 1, 1, 2, 3, 1 ]; let n = arr.length; let k = 2; if(checkCount(arr, n, k)) document.write("Yes"); else document.write("No"); </script> |
Output
Yes
Time Complexity: O(n^2)
Auxiliary Space: O(1)
Method 2:
- Maintain a hash for 32 different type of sweets.
- Traverse an array and check for every arr[i]
hash[arr[i]] <= 2*k.
Implementation:
C++
// C++ program for above implementation#include <bits/stdc++.h>using namespace std;// Function to check hash array// corresponding to the given arraybool checkCount(int arr[], int n, int k){ unordered_map<int, int> hash; // Maintain a hash for (int i = 0; i < n; i++) hash[arr[i]]++; // Check for each value in hash for (auto x : hash) if (x.second > 2 * k) return false; return true;}// Drivers codeint main(){ int arr[] = { 1, 1, 2, 3, 1 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; checkCount(arr, n, k) ? cout << "Yes" : cout << "No"; return 0;} |
Java
// Java program for above implementationimport java.util.HashMap;import java.util.Map;class GfG{ // Function to check hash array // corresponding to the given array static boolean checkCount(int arr[], int n, int k) { HashMap <Integer, Integer> hash = new HashMap<>(); // Maintain a hash for (int i = 0; i < n; i++) { if (!hash.containsKey(arr[i])) hash.put(arr[i], 0); hash.put(arr[i], hash.get(arr[i]) + 1); } // Check for each value in hash for (Map.Entry x : hash.entrySet()) if ((int)x.getValue() > 2 * k) return false; return true; } // Driver code public static void main(String []args) { int arr[] = { 1, 1, 2, 3, 1 }; int n = arr.length; int k = 2; if (checkCount(arr, n, k)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by Rituraj Jain |
Python3
# Python3 program for above implementation from collections import defaultdict# Function to check hash array # corresponding to the given array def checkCount(arr, n, k): mp = defaultdict(lambda:0) # Insert all array elements in # hash table Maintain a hash for i in range(n): mp[arr[i]] += 1 # Check for each value in hash for key, values in mp.items(): if values > 2 * k: return False return True# Driver codearr = [ 1, 1, 2, 3, 1 ]n = len(arr)k = 2if checkCount(arr, n, k) == True: print("Yes")else: print("No")# This code is contributed by Shrikant13 |
C#
// C# program for above implementationusing System; using System.Collections.Generic;class GfG{ // Function to check hash array // corresponding to the given array static Boolean checkCount(int []arr, int n, int k) { Dictionary<int,int> hash = new Dictionary<int,int>(); // Maintain a hash for (int i = 0; i < n; i++) { if(hash.ContainsKey(arr[i])) { var val = hash[arr[i]]; hash.Remove(arr[i]); hash.Add(arr[i], val + 1); } else { hash.Add(arr[i], 0); } } // Check for each value in hash foreach(KeyValuePair<int, int> x in hash) if ((int)x.Value > 2 * k) return false; return true; } // Driver code public static void Main(String []args) { int []arr = { 1, 1, 2, 3, 1 }; int n = arr.Length; int k = 2; if (checkCount(arr, n, k)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}/* This code is contributed by PrinciRaj1992 */ |
Javascript
// Function to check hash array// corresponding to the given arrayfunction checkCount(arr, n, k){ var hash = new Map(); // Maintain a hash for (var i=0; i < n; i++) { if (!hash.has(arr[i])) { hash.set(arr[i],0); } hash.set(arr[i],hash.get(arr[i]) + 1); } // Check for each value in hash for (let [key, value] of hash) { if (value > 2 * k) { return false; } return true; }}// Driver codevar arr = [1, 1, 2, 3, 1];var n = arr.length;var k = 2;if (checkCount(arr, n, k)){ console.log("Yes");}else{ console.log("No");}// This code is contributed by Aarti_Rathi |
Output
Yes
Time Complexity: O(n)
Auxiliary Space: O(n)
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!
