1
$\begingroup$

Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the goal is that you want to maximize the number of same-sized groups.

There can be multiple correct answers, and you can add to different groups (i.e. you can add 2 to one group, 3 to another, etc.)

Examples: group sizes:[1,1,1], able to add 7 objects Answer: 3, every group already has the same amount

[3,0,2,2,1], able to add 3 objects Answer: 4, you can add 2 objs to the group with 0, and 1 obj to the last group that has 1. So you maximize the 2's.

[5,4,1,3,4], able to add 2 objs Answer: 3, you can either add 1 obj to the group with 3, creating 3 4's, or you can add 1 to each of the groups of 4, creating 3 5's.

I can easily solve this using brute-force (for each number 1...n, where n is the max amount able to be added, try all possible combinations of adding to current groups and adding the number of newly created ones to the original total) but I am confused as to where the algorithmic optimization is. Have a nice day, thanks!

edit: put some example code of what I've tried.

#include <iostream>
#include <vector>
#include <map>

int maxCountOfEqualGroupSize(const std::vector<int>& groups, int objsToAdd) {

int maxGroupCount = 0;
std::map<int,int> groupSizeToGroupCount;
for (const auto& i : groups) {
  groupSizeToGroupCount[i]++;
}

//edge case - all groups already have the same size
auto iter = groupSizeToGroupCount.begin();
int firstVal = iter->second;
bool foundDiff = false;
for (; iter != groupSizeToGroupCount.end(); ++iter) {
  if (iter->second != firstVal) {
    foundDiff = true;
    break;
  }
}

if (!foundDiff) {
  return groups.size();
}
//end edge case

//find biggest value and get that key
//Then advance that key one by one to the right
//for each iteration: start at that key, and start moving left
//filling groups in, once you run out of objs to fill with,
//terminate.
int maxKey;
for (const auto& p : groupSizeToGroupCount) {
  if (p.second > maxGroupCount) {
    maxGroupCount = p.second;
    maxKey = p.first;
  }
}


auto startIter = groupSizeToGroupCount.find(maxKey);
auto lastIter = groupSizeToGroupCount.rbegin();
auto firstIter = groupSizeToGroupCount.begin();

for (; startIter->first != lastIter->first; ++startIter) {
  int objCounter = objsToAdd;
  int runningGroupCount = startIter->second;

  auto startPoint = --startIter;
  ++startIter;
  for(auto goingLeft = startPoint; 
     objCounter >= 0; 
     --goingLeft) {

    int diff = startIter->first - goingLeft->first;
    int groupsToFill = goingLeft->second;
    int amountToAdd = groupsToFill * diff;
    if (amountToAdd > objCounter) {
      //add up to what we can, since we can't fill all the groups
      while (objCounter >= diff) {
        ++runningGroupCount;
        objCounter -= diff;
      }
    } else {
      objCounter -= amountToAdd;
      runningGroupCount += groupsToFill;
    }
    
    if (goingLeft == firstIter) {
        break;
    }
  }
  maxGroupCount = std::max(maxGroupCount, runningGroupCount);
}
return maxGroupCount;
}

int main() {
  std::vector<int> ttt = {1,1,1};
  std::vector<int> tt = {3,0,2,2,1};
  std::vector<int> t = {5,4,1,3,4};
  std::cout << maxCountOfEqualGroupSize(t, 2) << std::endl;
  std::cout << maxCountOfEqualGroupSize(tt, 3) << std::endl;
  std::cout << maxCountOfEqualGroupSize(ttt, 2) << std::endl;

}
$\endgroup$
3
  • 1
    $\begingroup$ Can you credit the source where you originally encountered this task? $\endgroup$
    – D.W.
    Sep 20, 2020 at 7:41
  • $\begingroup$ looks like someone else solved it here :) leetcode.com/discuss/interview-question/856945/… $\endgroup$ Sep 29, 2020 at 5:27
  • $\begingroup$ Please do not delete your question if you have found a solution elsewhere, we want to keep your question to help others find a solution to the same problem. Also, you can answer your own question with a summary of your final approach, if you want to. $\endgroup$
    – Discrete lizard
    Sep 29, 2020 at 10:15

1 Answer 1

1
$\begingroup$

Hint:

Try working through some examples. Can you narrow down the set of possible values that might appear in the largest group in the best solution? (For instance, your second example has 2's as the value, and your third example has 4's or 5's.) Can you see how to use that to help you do better than brute force?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.