Equal Candy Bar Moves
MediumMath · Walmart
You have three types of candy with counts a, b, and c. In one move you pick two different types that each have at least one candy, remove one candy from each of them, and add two candies to the third type.
For example, picking the first and third types turns [a, b, c] into [a - 1, b + 2, c - 1]. The total number of candies never changes.
Return the minimum number of moves needed to make all three counts equal, or -1 if it is impossible. The counts can be very large, so simulating moves one by one or searching over states is too slow.
Example 1
- Input:
- a = 1, b = 1, c = 4
- Output:
- 2
- Explanation
- Pick the first and third types to get
[0, 3, 3], then the second and third to get[2, 2, 2]. One move cannot do it, since every move changes all three counts.
Example 2
- Input:
- a = 5, b = 2, c = 8
- Output:
- 3
- Explanation
- The target is 15 / 3 = 5 of each. The third type must lose 3 candies and loses at most one per move, so at least 3 moves are needed. Picking the first and third types twice gives
[3, 6, 6], then the second and third gives[5, 5, 5].
Example 3
- Input:
- a = 2, b = 3, c = 4
- Output:
- -1
- Explanation
- Each move changes every count by
-1or+2, which shifts all three remainders mod 3 by the same amount.2, 3, 4have different remainders mod 3, so they can never become equal.
Constraints
0 <= a, b, c <= 10^8