[Java/C++/Python] max(max(A), (sum(A) + 1) / 2)
Explanation\nIt\'s a brain-teaser.\n\nNecessary conditions (lower bound)\n1. res >= max(A)\nBecause each time,\none type can reduce at most 1 cup,\nso the final
# **Explanation**\nIt\'s a brain-teaser.\n\n**Necessary conditions (lower bound)**\n1. `res >= max(A)`\nBecause each time,\none type can reduce at most 1 cup,\nso the final result is bigger or equal to `max(A)`\n\n2. `res >= ceil(sum(A) / 2)`\nBecause each time,\nwe can fill up to 2 cups,\nso the final result is bigger or equal to `ceil(sum(A) / 2)`\n\n**Sufficient considtion (realizeable)**\nOne strategy is to greedily fill up 2 cups with different types of water.\nEach step, we pick the 2 types with the most number of cups, until there is only one kind.\n\n**Conclusion**\nThe lower bound is realizable,\nso it\'s proved as the minimum steps.\n<br>\n\n# **Complexity**\nTime `O(n)`\nSpace `O(1)`\n<br>\n\n**Java**\n```java\n    public int fillCups(int[] A) {\n        int mx = 0, sum = 0;\n        for(int a: A) {\n            mx = Math.max(a, mx);\n            sum += a;\n        }\n        return Math.max(mx, (sum + 1) / 2);\n    }\n```\n\n**C++**\n```cpp\n    int fillCups(vector<int>& A) {\n        int mx = 0, sum = 0;\n        for(int& a: A) {\n            mx = max(a, mx);\n            sum += a;\n        }\n        return max(mx, (sum + 1) / 2);\n    }\n```\n\n**Python**\n```py\n    def fillCups(self, A):\n        return max(max(A), (sum(A) + 1) // 2)\n```\n
['C', 'Python', 'Java']