Forum

Post 28.04.2009   # 1
Subject 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+(N-1)) = L*N + (N-1)*N/2
sum - the sum of the numbers, after one of them was erased: sum = originalSum - L - x = L*N + (N-1)*N/2 - L - x = L*(N-1) + (N-1)*N/2 - x
or: sum - (N-1)*N/2 = L*(N-1) - x
Here we can define new variable, temp:
temp = sum - (N-1)*N/2 ... (1) or:
temp = L*(N-1) - 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 N-1.
remainder = temp % (N-1), or x = N - 1 - remainder.
Now we can calculate L = (temp + x) / (N-1)
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 = N-1-remainder, we have to test if the remainder is equal to 0, and in that case, x = 0.

This is the whole solution:
public class ErasedNumber {
public int findErased(int N, int sum) {
int temp = sum - (N * (N-1)) / 2;
int remainder = temp % (N-1);
int x = (remainder == 0 ? 0 : N - 1 - remainder);
int L = (temp + x) / (N-1);
return L + x;
}
}
bilievsk is offline Reply

Please login to post reply.