2591. Distribute Money To Maxi...

This page provides solutions for the leetcode problem 2591. Distribute Money to Maximum Children.

Problem Explanation

The problem is asking us maximize the number of children who receive exactly $$8$ if we distribute the $\text{money}$ among $\text{children}$ under the following conditions:

• All money must be distributed.
• Everyone must receive at least 1 dollar.
• Nobody receives 4 dollars.

Solution

This problem can be solved using the Binary Search technique. More such questions can be found here.

Java

class Solution {
  public int distMoney(int money, int children) {
    int lo = -1;
    int hi = children;
    while(lo < hi) {
      int mid = (lo + hi + 1) / 2;
      if(isValid(money, mid, children)) lo = mid;
      else hi = mid - 1;
    }
    return lo;
  }

  private boolean isValid(int money, int maxChlidren, int children) {
    int remainingMoney = money - 8 * maxChlidren;
    int remainingChildren = children - maxChlidren;
    if(remainingMoney == 4 && remainingChildren == 1) return false;
    else if(remainingMoney < remainingChildren) return false;
    else if(remainingMoney > 0 && remainingChildren == 0) return false;
    else return true;
  }
}

Complexity

Let's say $\text{N}$ be the total amount of money to be distributed among $\text{K}$ children.

Time Complexity

The time complexity is $\text{O}(\log \text{K})$ for searching the optimal solution using binary search.

$$\text{O}(\log \text{K})$$

Space Complexity

The solution uses constant space for storing binary search variables.

$$\text{O}(1)$$