CareerCup

sum(a to b)

b(b+1)/2 - a(a+1)/2

(b^2 +b - a^2 -a)/2

(b^2 - a^2 + b -a)/2

( (b+a) (b-a) + (b-a) )/2

(b-a) [ (b+a) + 1] /2

Are we missing the "+1" in the above solution you have provided.

private int MissingNumberFinder(int a , int b , int[] array)
{
int OriginalSum = 0;
int Sum = 0;
OriginalSum = (array.Length +1) * ((a + b) / 2 );

foreach(int number in array)
{
Sum += number;
}
return OriginalSum - Sum;
}

guys why wasting time on silly problems...just XOR the numbers and what remains at the end is the missing number.coool isn't it!!!

This solution doesn't work. For example if the some from 2 to 8 was to be calculated it would be 2+3+4+5+6+7+8 = 35
where as this gives you 33.
It misses out the 2.
So we need to add a to (b-a)[(b+a) +1]/2

I think it is because we do (sum of 1 to b) minus (sum of 1 to a). When subtracting sum of 1 to a we are subtracting the a. The sum has to be from a to b.

Good, but it shouldn't be array.Length + 1. Also, as a programming note, there is no reason to initialize OriginalSum to 0 when you can already determine its value.

The sum of the numbers from a to b, inclusively, is (b - a + 1) * (a + b)/2, array.Length being (b - a + 1).


Therefore,

OriginalSum = (array.Length) * (a + b)/2;

or

OriginalSum = (b - a + 1) * (a + b)/2;

The Sum Should be: (b-a)/2*(b+a+1)

The calculation is as follows:
Sum(a..b) = Sum (1..b) - Sum (1..a) =
b(b+1)/2 - a(a+1)/2 =
(b^2 + b - a^2 - a)/2 =
(b^2-a^2) + (b-a)/2 =
(b-a)(b+a)+(b-a)/2 =
(b-a)[(b+a) + 1]/2=
(b-a) (b+a+1) /2 =>>>>>>>>>>
array.length * (b+a+1)/2

The Sum Should be: (b-a)/2*(b+a+1)

The calculation is as follows:
Sum(a..b) = Sum (1..b) - Sum (1..a) =
b(b+1)/2 - a(a+1)/2 =
(b^2 + b - a^2 - a)/2 =
(b^2-a^2) + (b-a)/2 =
(b-a)(b+a)+(b-a)/2 =
(b-a)[(b+a) + 1]/2=
(b-a) (b+a+1) /2 =>>>>>>>>>>
(array.length-1) * (b+a+1)/2

for ex. if a=5 and b=7 then: b-a = 7-5 = 2. however the array includes the elements: 5,6,7 => array.length = 3 => b-a = array.length -1

Please, correct me if i am wrong.

Sum of original list from a to b
(b-a)[(b+a+1)/2]

MINUS

Sum of list from a to b after removal of an element
(b-a)[(b+a+1)/2]

should give the missing number

The sum formula from a to b should be:
(b-a+1)*(a+b)/2, not (b-a)*(a+b+1)/2.

Eila's intuition missed one point that the
sum(a..b) should be sum(1..b)-(1..a-1), not sum(1..b)-(1..a).

This sum formula could be easily remembered as the number of integers multiple by the average of the first integer and the last integer.

The key idea of this problem is just as Sunil said, using the original sum substracts the actual sum, then you get the missing number.

Assuming n,m are positive...

The +/- sides have symmetry. Hence, 1 to n is n(n+1)/2 and -1 to -m is -m(m+1)/2, and 0. By symmetry, the sum should be 0.

If you remove a negative A, add -A. Similarly for positive A.

...if the interval isn't balanced...

Suppose you have [-2,8]...

By the above solution, you may try -1 to -8. You then have an unused interval of [-8,-3]. However, you can do the following arithmetic...

-3 + -4 + -5 + -6 + -7 + -8=-1(3+4+5+6+7+8)
-1(3+4+5+6+7+8 - 2*6)=-1(1+2+3+4+5+6)=-1 * m(m+1)/2.

Taking the XOR of all no.s is the better soln.

int xor1,xor2,missing_no;

for(int i=0;i<(b-a);i++) //taking the XOR of all the no.s
xor1^=arr[i];//array.length = b-a+1 (but one no. is missing
// so actual length becomes 1 less i.e array.length= b-a;

for(int i=a;i<=b;i++)
xor2^=i;

missing_no=xor1^xor2;
cout<<"Missing No is : "<<missing_no;

A useful formula to memorize is the arithemetic series formula:

Sn = a1 + a2 + a3 + ... + an = n * (a1 + an)/2 = n * (2 * a1 + (n - 1) * d) / 2

Note that Sn, a1, a2, a3 and an have 1,2,3,n subscripted. The d above is the common difference between the terms (d = a2 - a1, d = a3 - a2, etc.).

For this problem, a is a1, and b is an, and d is 1. The number of terms, n, is (an - a1 + 1). Soooo, substituting into the formula:

Sn = n * (a1 + an)/2           where n = (an - a1 + 1)

Sn = (an - a1 + 1) * (a1 + an) / 2      where a1 = a and an = b for our problem

Sn = (b - a + 1) * (a + b) / 2

Please see en.wikipedia.org/wiki/Arithmetic_progression for more information.

sum(a to b)

Sum(a to b) - Sum [1 to (a-1)]

b(b+1)/2 - { (a-1)(a - 1 + 1)/2 }

(b^2 + b)/2 - [(a^2-a)/2]

(b^2 + b - a^2 + a)/2

(b^2 - a^2 + b + a)/2

( (b+a) (b-a) + (b+a) )/2

(b+a) [(b-a) + 1] /2

We can test the same with expample some from 2 to 8.

it should be

Sum(a to b) = Sum(1 to b) - sum(1 to (a -1))
= b(b+1)/2 - ((a-1)(a/2))