Find Missing Number in a Range- Javascript challenge

Question

Can someone help me get started on this challenge:

Given an array of 99,999 unique numbers ranging from 1 to 100,00 in a random order, find the one number that is missing from the list.

I'm not sure how to start thinking about it.

You should re-phrase the question and also provide some attempts. — , Jun 13 '15 at 10:26
how are you filling 10000 integers in an array of 99999 withour repitition — bugwheels94, Jun 13 '15 at 10:28
@Ankit: I think that's a typo, I think it's 1 to 100,000 -- but of course, you can do the other, as well, they just won't be *whole* numbers. — T.J. Crowder, Jun 13 '15 at 10:30
Rory, did you mean 1 to 100,000 rather than 1 to 100,00? (That latter doesn't make sense if `,` is the thousands separator, but in some locals it's a decimal point, so...) — T.J. Crowder, Jun 13 '15 at 10:30

score 7 · Accepted Answer · edited Jun 13 '15 at 10:38

7

Except for the missing number, you are describing an arithmetic progression, which has a nifty formula to calculate its sum. So you could loop over the array, sum it, and then subtract that from the formula. The difference would be the missing element:

function missing(arr) {
    var sum = 0;
    for (var i = 0, len = arr.length; i < len; ++i) {
        sum += arr[i];
    }
    var expected = 100000 * (1 + 100000) / 2;
    var missing = expected - sum;
    return missing;
}

edited Jun 13 '15 at 10:38

T.J. Crowder

1,031,962
187
1,923
1,875

answered Jun 13 '15 at 10:30

Mureinik

297,002
52
306
350

2

A bit more than just helping OP to start thinking of the problem themselves, but yes it's correct – jamylak Jun 13 '15 at 10:31
1

I think you mean `arr[x]` in the loop? – Gaurang Tandon Jun 13 '15 at 10:32
2

Don't use `for in` to loop through arrays, or if you do, use safeguards. [Better options in this answer.](http://stackoverflow.com/questions/9329446/for-each-over-an-array-in-javascript/9329476#9329476) – T.J. Crowder Jun 13 '15 at 10:32
@NiklasB. - yup, was missing the `/2`, edited. Thanks for noticing! – Mureinik Jun 13 '15 at 10:33
1

@T.J.Crowder just making my first steps in JS, thanks for the insight. I went back to the old fashioned `for` loop - as you mentioned, sometimes, the old ways are the best ways. – Mureinik Jun 13 '15 at 10:36
line 3: a is not defined, there must be arr – Serg Jun 13 '15 at 10:37
@Serg the copy-and-bug idiom :-) lost concentration there for a minute, thanks! – Mureinik Jun 13 '15 at 10:37
3

@Mureinik: :-) I hate to say it, but now you're falling prey to [*The Horror of Implicit Globals*](http://blog.niftysnippets.org/2008/03/horror-of-implicit-globals.html). I've taken the liberty of fixing it for you. – T.J. Crowder Jun 13 '15 at 10:38

jamylak · Answer 2 · 2015-06-13T10:43:56.567

5

If you want to do it without wasting any space storing numbers,

start with 1+2+3+4+... sum

Then subtract each number in the array from the sum

edited Jun 13 '15 at 10:43

answered Jun 13 '15 at 10:29

jamylak

128,818
30
231
230

Find Missing Number in a Range- Javascript challenge

2 Answers2