Distribute items such that a person cannot take more than two items of the same type

Implementation in c++

#include <bits/stdc++.h>
using namespace std;


/* Function to check hash array
 corresponding to the given array */
bool check(int arr[], int n, int k) {
unordered_map<int, int> t;
/* Maintaining a hash for the array */
for (int i = 0; i < n; i++)
t[arr[i]]++;
/* Checking for each value in hash */
for (auto x : t)
if (x.second > 2 * k)
return false;
return true;
}


int main() {
int arr[] = { 1, 1, 2, 3, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
check(arr, n, k)?cout << "Yes":cout << "No";
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Yes

You can also try this code with Online Java Compiler

Run Code

Implementation in Java 

// Java program for above implementation
import java.util.HashMap;
import java.util.Map;


class HelloWorld {
/* Function to check hash array
  corresponding to the given array */
static boolean check(int arr[], int n, int k)
{
HashMap <Integer, Integer> hash = new HashMap<>();

/* Maintaining 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);
}

/* Checking for each value in hash */
for (Map.Entry x : hash.entrySet())
if ((int)x.getValue() > 2 * k)
return false;

return true;
}


public static void main(String []args)
{

int arr[] = { 1, 1, 2, 3, 1 };
int n = arr.length;
int k = 2;
if (check(arr, n, k))
System.out.println("Yes");
else
System.out.println("No");
}
}

Output

Yes

You can also read about the Longest Consecutive Sequence.

Complexity Analysis

Time Complexity

O(N), Where ‘N’ stands for the array's length.

Reason: We are using only two loops, one while hashing and the other while checking the value in the hash.

Space Complexity

O(N), Where ‘N’ stands for the array's length.

Reason: Even in the worst-case scenario, the maximum length of the hash can be up to the array's size.

Frequently Asked Questions

Explain hashing?

Hashing can transform any key or string of characters into another value. The original string is typically represented with a shorter, fixed-length value or key, making it simpler to locate or use.

What do you mean by a hash key?

A form of data structure that contains key-value pairs is a hash table. A hash function receives the key and runs mathematical operations on it.

What is the DP?

Dynamic programming, often known as DP, is an algorithmic technique for solving problems by recursively dividing them into easier subproblems and taking advantage of the fact that the best solution to the whole problem depends on the best solution to each of its subproblems.

What is the purpose of hashing?

Data is mapped to a fixed-length value using the one-way function of hashing. Authentication is the main purpose of hashing. Salting is an extra step in the hashing process that adds an extra value to the end of the password to alter the hash value that is generated. It is commonly used in conjunction with hashed passwords.

Why is hashing quicker?

The linear time complexity of O(n) is presented when searching through an array-like data structure. In other words, the search time grows linearly in proportion to the size of the data structure.

Conclusion

In this article, we have discussed the question related to array and hashing. Distribute items such that a person cannot take more than two items of the same type in multiple languages.

Want to learn data structure in java language click here.
Check out this problem - Two Sum Problem

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.
Do upvote our blog to help other ninjas grow.
Happy Learning!