LintCode 1671 · play game.java

	public class Solution {
	/**
	* @param A:
	* @return: nothing
	*/
	public long playGames(int[] A) {
	// handle corner cases
	if (A == null || A.length == 0) {
	return 0;
	}
	long begin = 0, end = A.length;
	// find the begin and end for the binarySearch
	for (int a : A) {
	if (begin < a) {
	begin = a;
	}
	end += a;
	}
	// binarySearch on the solution space
	while (begin + 1 < end) {
	long mid = (end - begin) / 2 + begin;
	if (isValid(A, mid)) {
	end = mid;
	} else {
	begin = mid;
	}
	}
	if (isValid(A, begin)) {
	return begin;
	} else {
	return end;
	}
	}
	private boolean isValid(int[] A, long games) {
	return getRoundsOfJudges(A, games) >= games;
	}
	private long getRoundsOfJudges(int[] A, long games) {
	long sum = 0;
	for (int a : A) {
	sum += (games - a);
	}
	return sum;
	}
	}

view raw LintCode 1671 · play game.java hosted with ❤ by GitHub