Tutorialspoint.dev

Distributing items when a person cannot take more than two items of same type

Given N sweets which can be of many different types and k customers, one customer won’t take the same type of sweet more than 2 pieces, the task is to find if it is possible to distribute all sweets then print “Yes” otherwise “No”.

Given array arr[] represents 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 : No


Method 1:
1- Traverse array for each element.
2- Count occurrences of each element in array
3- Check Resulting occurrence of each element must be less than or equal to 2*k.

C++

// C++ program for above implementation
#include <bits/stdc++.h>
using namespace std;
  
// Function to check occurrence of each element
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
int 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 implementation
import 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 code
arr = [1, 1, 2, 3, 1]
n = len(arr)
k = 2
if checkCount(arr, n, k) == True:
    print("Yes")
else:
    print("No")
  
# This code is contributed by Shrikant13

C#

// C# program for above implementation
using 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 element
function 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.
?>


Output:

Yes

Time Complexity: O(n^2)

 

Method 2:
1. Maintain a hash for 32 different type of sweets.
2. Traverse an array and check for every arr[i]

hash[arr[i]] <= 2*k. 

C++

// C++ program for above implementation
#include <bits/stdc++.h>
using namespace std;
  
// Function to check hash array
// corresponding to the given array
bool 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 code
int 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;
}

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 code
arr = [ 1, 1, 2, 3, 1 ]
n = len(arr)
k = 2
if checkCount(arr, n, k) == True:
    print("Yes")
else:
    print("No")
  
# This code is contributed by Shrikant13 


Output:

Yes

Time Complexity: O(n)



This article is attributed to GeeksforGeeks.org

tags:

Hash Hash

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter