## Intuition The problem revolves around redistributing candies among friends such that each friend ends up with the same number of candies. The key insight is to determine if it's possible to make all the candies equal by redistributing some of them. If possible, we need to find the minimum number of friends from whom we can take candies to achieve this uniform distribution. ## Approach 1. **Calculate Total Candies and Check Divisibility**: - First, compute the total number of candies across all friends. - Check if this total is divisible by the number of friends `n`. If not, it's impossible to make all candies equal, and we should return `-1` for that test case. 2. **Determine Target Candies per Friend**: - If divisible, calculate the target number of candies each friend should have, which is `total_candies / n`. 3. **Count Friends with Excess Candies**: - Iterate through the list of candies. Count the number of friends who have more candies than the target. These are the friends from whom we can redistribute excess candies. 4. **Output the Result**: - The count of friends with excess candies is the minimum number of friends `k` from whom we need to take candies to achieve the desired distribution. ## Complexity - **Time Complexity**: O(n) per test case, where `n` is the number of friends. We iterate through the list of candies once to calculate the total and once more to count excess candies. - **Space Complexity**: O(1), as we use a constant amount of extra space. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); long long total_candies = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; total_candies += a[i]; } if (total_candies % n != 0) { cout << -1 << '\n'; } else { int target = total_candies / n; int count_excess = 0; for (int i = 0; i < n; ++i) { if (a[i] > target) { count_excess++; } } cout << count_excess << '\n'; } } return 0; } ``` This solution efficiently calculates the minimum number of friends from whom candies need to be redistributed to achieve an equal distribution among all friends. It handles multiple test cases and outputs the correct result for each.

Friends and Candies

Problem Details