CareerCup

google Find Missing Term In Arithmetic Progression

I think there's still one thing to consider. For each round, as to the number of 0s -- N, we have two cases: [1] N = N-1, that's we move 0 in 1th bucket to 0th bucket. [2]N = N, move 0 in ith bucket to (i-1)th bucket, here i>=2. And for each player, he'll try to keep N (remaining number of 0s after his round) to be even, so that he can always take the last round. I think this is what "play optimally" means in the question. So, we have

int finder(ArrayList<Integer> buckets, int player){
	if (buckets.size()==1)
		return getOpponent(player);
	int N = getTotalNumberOfZeros(buckets, 1, buckets.size()-1);
	if (buckets.size()==2)
		return N%2==0 ? getOpponent(player): player;
	if (N%2!=0){
		moveZeroWithoutDecrement();
	}else{
		if (!1thBucketIsEmpty())
			moveZeroWithDecrement();
		else
			moveZeroWithoutDecrement();
	}
	return finder(buckets, getOpponent(player));
}

@Zero2, actually no need to check ascending or descending order here. We use 'start' and 'end'. If actualValue[mid] == expectedValue[mid], start=mid+1; otherwise, end = mid.

aj's solution is correct. But the final traversal to check whether all cells have been visited is not necessary. We can maintain a variable 'count' to hold the number of visited cells. When we encounter a visited cell, just check 'count==M*N'

I hold reservation about the answer. Value of an array can be accessed by offset, too. See the discussion here. h-t-t-p://stackoverflow.com/questions/5445131/why-are-linked-lists-faster-than-arrays