hi, let Avik connect you.

** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Minimum Rounds to Complete All Tasks

Problem: 2244. Minimum Rounds to Complete All Tasks
Problem Link: https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/
Companies Asked: Amazon

Approach:
1. Start traversing through the given list of durations.
2. Counted them and stored them in a HashMap.
3. Now traverse the HashMap.
4. As we need to reduce the round, we will take the remainder of dividing the count by 3.
5. If the remainder comes out as 0, then we simply can complete by doing 3 tasks on every round. So, count / 3 will be added to the total result.
6. If the remainder is 2, then we can complete one round by doing 2 tasks. So, (count/3 + 1) will be added to the total result.
7. If the remainder is 1, we can not complete by doing 1 task as we can do only 2 / 3 tasks at a time.
8. What we can do is complete (count / 3 - 1) tasks by doing 3 tasks at a time and do the remaining 2 tasks by doing 2 tasks at a time. So, (count / 3 - 1) + 2 will be added to the result.
9. Return the result.

Time and Space Complexity:
- - Time Complexity: O(N)
  - Space Complexity: O(N)

Code [C++] (HashMap) [ O(N) / O(N) ]

class Solution {

public:

int minimumRounds(vector<int>& tasks) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

unordered_map<int, int>ucount;

int n = tasks.size(), total = 0;

for(int i=0; i<n; i++){

ucount[tasks[i]]++;

}

for(auto it=ucount.begin(); it!=ucount.end(); ++it){

if(it->second <= 1) return -1;

int remainder = (it->second) % 3;

if(remainder < 2) total += (it->second / 3) + remainder;

else total += ((it->second / 3) - 1) + 2;

}

return total;

}

};

Code [C++] (Sorting + Counting) [ O(Nlog2N) / O(1) ]

class Solution {

public:

int minimumRounds(vector<int>& tasks) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

sort(tasks.begin(), tasks.end());

int n = tasks.size(), cnt = 1, total = 0;

for(int i=0; i<n-1; i++){

if(tasks[i] == tasks[i+1]){

cnt++;

}

else{

if(cnt < 2) return -1;

int remaining = cnt % 3;

if(remaining == 0) total += (cnt / 3);

else if(remaining == 2) total += (cnt / 3) + 1;

else total += (cnt / 3) - 1 + 2;

cnt = 1;

}