Forum
28.04.2009  # 1 
CodeFu 2009 Round 1  Problem 400
400. Erased Number
This problem can be solved by first doing some mathematics. Lets define the following variables: L  the smallest number that was written on the board x  the index of the number that was erased (0 based, so if the first number was erased, then x = 0) L+x  the value of the erased number (this is what the method should return). originalSum  the sum of all the N numbers, before erasing one of them: originalSum = L + (L+1) + (L+2) + ... + (L+(N1)) = L*N + (N1)*N/2 sum  the sum of the numbers, after one of them was erased: sum = originalSum  L  x = L*N + (N1)*N/2  L  x = L*(N1) + (N1)*N/2  x or: sum  (N1)*N/2 = L*(N1)  x Here we can define new variable, temp: temp = sum  (N1)*N/2 ... (1) or: temp = L*(N1)  x ... (2) Since we know the values for sum and N we can calculate how much is temp using the first of the above equations. Then using the second equation, we can get x by first calculating the remainder when dividing temp with N1. remainder = temp % (N1), or x = N  1  remainder. Now we can calculate L = (temp + x) / (N1) And finally return the erased number, which is: L + x One note about the case when there are two possible solutions. This can happen if the first or the last number from the sequence was deleted. For example: if the input was: N=4, sum=15. The only solution for the sum is: sum = 4 + 5 + 6. This can happen if either the sequence was 3,4,5,6 and 3 was erased, or the sequence was 4,5,6,7 and 7 was erased. To solve this issue, when calculating x = N1remainder, we have to test if the remainder is equal to 0, and in that case, x = 0. This is the whole solution:


Please login to post reply.