[ Kotlin | Java | C++ | Python ] Simple Binary Search solution, detailed explanation
IntuitionThis is a classic application of binary search on the answer space. The problem asks us to find the maximum number of candies that can be allocated to
# Intuition
This is a classic application of binary search on the answer space. The problem asks us to find the maximum number of candies that can be allocated to each child, where:
1. Each child must get the same number of candies
2. Candies can only be taken from a single pile per child
3. Piles can be divided but not merged
4. Some piles may remain unused

Since we want to maximize the number of candies per child, we can try different possible answers and check their feasibility. The key insight is that if we can allocate x candies to each child, we can also allocate any number less than x. This monotonic property makes binary search an ideal approach.

# Approach
1. Define a search space for the possible number of candies per child:
   - Minimum: 1 (since we can't give 0 candies if a valid solution exists)
   - Maximum: The maximum value in the candies array (since we can't give more than the largest pile)

2. Implement a `check(value)` function that determines if it's possible to give `value` candies to each of the `k` children:
   - For each pile of size `candies[i]`, we can create `candies[i] / value` sub-piles of size `value`
   - Sum up the total number of sub-piles we can create across all piles
   - If this sum is at least `k`, then we can give `value` candies to each child

3. Use binary search to find the maximum valid value:
   - If `check(mid)` is true, search in the right half (mid+1, right)
   - Otherwise, search in the left half (left, mid)

4. When the binary search terminates, we need to subtract 1 from the result since our algorithm finds the smallest value that does NOT work, so we need to return the previous value.

5. Special case: If the total number of candies is less than `k`, return 0 as it's impossible to give each child at least 1 candy. This is handled implicitly by our binary search, which will return 1-1=0.

# Complexity Analysis

## Time Complexity: $$O(N log M)$$
- `N` is the number of piles (length of the candies array)
- `M` is the maximum value in the candies array
- The binary search performs `log M` iterations
- For each iteration, we check all `N` piles in the worst case

## Space Complexity: $$O(1)$$
- We only use a constant amount of extra space regardless of the input size
- The recursive calls in the binary search use $$O(log M)$$ stack space, but this can be converted to an iterative solution with $$O(1)$$ space

# Code
```kotlin []
class Solution {
    fun maximumCandies(candies: IntArray, k: Long): Int {
        fun check(value: Int) = candies.sumOf { it.toLong() / value } >= k

        fun binSearch(left: Int = 1, right: Int = candies.max() + 1): Int {
            if (left >= right) return right
            val mid = left + (right - left) / 2
            return if (check(mid)) binSearch(mid + 1, right) else binSearch(left, mid)
        }

        return binSearch() - 1
    }
}
```

```java []
class Solution {
    private static final int MAX = 10_000_001;

    public int maximumCandies(int[] candies, long k) {
        return binSearch(candies, k, 1, MAX) - 1;
    }
    
    private boolean check(int[] candies, long k, int value) {
        long sum = 0;
        for (int candy : candies) {
            sum += (long) candy / value;
        }
        return sum >= k;
    }
    
    private int binSearch(int[] candies, long k, int left, int right) {
        if (left >= right) return right;
        
        int mid = left + (right - left) / 2;
        
        return check(candies, k, mid) 
            ? binSearch(candies, k, mid + 1, right) 
            : binSearch(candies, k, left, mid);
    }
}
```

```cpp []
class Solution {
private:
    static const int MAX = 10000001;
    
    bool check(vector<int>& candies, long long k, int value) {
        long long sum = 0;
        for (int candy : candies) {
            sum += (long long)candy / value;
        }
        return sum >= k;
    }
    
    int binSearch(vector<int>& candies, long long k, int left, int right) {
        if (left >= right) return right;
        
        int mid = left + (right - left) / 2;
        
        return check(candies, k, mid) 
            ? binSearch(candies, k, mid + 1, right) 
            : binSearch(candies, k, left, mid);
    }

public:
    int maximumCandies(vector<int>& candies, long long k) {
        return binSearch(candies, k, 1, MAX) - 1;
    }
};
```

```python3 []
class Solution:
    def maximumCandies(self, candies: list[int], k: int) -> int:
        MAX = 10_000_001
        
        def check(value: int) -> bool:
            return sum(candy // value for candy in candies) >= k
        
        def binSearch(left: int, right: int) -> int:
            if left >= right:
                return right
            
            mid = left + (right - left) // 2
            
            return binSearch(mid + 1, right) if check(mid) else binSearch(left, mid)
        
        return binSearch(1, MAX) - 1
```
['Array', 'Binary Search', 'Python', 'C++', 'Java', 'Python3', 'Kotlin']