# Non-Duplicate Integer Arrays

A typical question asked in "History of JavaScript" classes where the teacher mistakenly believes they are teaching programming.

### Question:

Use a one-dimensional array to solve the following problem: Read in 20 numbers, each of which is between 10 and 100. As each number is read, print it only if it is not a duplicate of a number that has already been read. Provide for the "worst case", in which all 20 numbers are different. Use the smallest possible array to solve this problem.

With this question we are not going to look at the historical answer but rather at how we can create a modern solution that meets all (or at least almost all) of the irrelevant information that is set down in the criteria. In this case we will disregard the criteria or printing the unique values as they are read and print them all at the end. We will however comply with all of the other criteria.

This particular problem is obviously one that was written for JavaScript beginners back in the 20th Century. The approach that would have been taken back then would have involved a loop using prompt to input all of the numbers. These numbers would have then needed to be validated to ensure they were integers between 10 and 100 and ignored if they were not. If integers they would then be compared to the values already saved in the array and added to the array (and printed) if that value was not already saved.

Instead of just answering the question as intended for JavaScript Zero use, we will instead imagine that we are creating a non-duplicate-array object that we need to test. By creating both the object and unit test code to test it with we can produce code that meets the original criteria in a useful way since the object can then be plugged into real code in the real world and it doesn't matter if we use prompt for testing as that is what it has always mainly been intended for anyway.

The object is created using two values to define the range of positive integers that the non-duplicate array will be allowed to hold. It uses an array to hold the values and that array will only ever contain as many entries as there are non-duplicate integers within the range that are entered (meeting the smallest array criteria - although not in the way the original question would have expected). The object has a set() method where a value is passed to the object. That value is then tested to ensure it is an integer in the specified range and false is returned if it isn't. If it is in the range then that integer is added to the array and false is returned. If the integer was already in the array then the new entry simply overwrites the existing one so we don't need to test for duplicates. The object also has a getAll() method that returns an array of the saved values.

Here is our non-duplicate array object:

``var ndArray = function(a,b) {this.a = a;this.b = b;this.n = [];};ndArray.prototype.set = function(n) {if (n != +n || n%1 != 0 || n < this.a || n > this.b) return false;this.n[n] = "";return true;};ndArray.prototype.getAll = function() {return Object.keys(this.n);};``

Now that code looks nothing whatever like what the teacher asking the original question would expect to have provided in the answer but that object with its set() and getAll() methods does actually do everything it needs to including validating that the values entered are in fact integers within a specified range. It discards the duplicates and the getAll() method will return the smallest array that can contain the non-duplicates.

To answer the original question (except for printing all the entries at the end instead of along the way) we can set up a unit test for testing our new object. For this purpose we can legitimately use prompt() for reading in the values for the test. As it is just a test we can use console.log() to output the result as a comma separated list.

``var x = new ndArray(10,100);var i = 0;while (i < 20) {if (x.set(prompt('Enter an integer between 10 and 100'))) i++;}console.log(x.getAll().join(','));``

The entire code does exactly what the original question asks in a way that uses the loop and prompt that the teacher is expecting but it does it in a way that uses much less code than they are probably expecting. So let's examine the code in more detail to see how it works

Our unit test code creates an ndArray() object specifying 10 and 100 as the valid range of positive integers. We then set up a while loop to read in the 20 integers within that range. The prompt() call reads in a value. We pass the value entered to the set() method and if it is an integer within the range the method saves the value and returns true so the loop counter gets incremented. If it is not an integer or is outside the range the value isn't saved and the method returns false so that the loop counter isn't incremented. Once 20 valid integers within the range have been processed the getAll() method is called to write out all the non duplicates.

The way that this code tests for duplicates is that it doesn't save the integers as values in the array, it instead saves them as keys in the array. Each entry in an array has a key and a value. The keys in an array are integers between 0 and 4294967295 so if we are concerning ourselves with positive integers that are all smaller than four billion we can save them as array keys instead of as array values. This has the benefit in this case of removing the need to check for duplicates since two or more entries with the same key are the same entry. Effectively what we are creating is a sparse array where the number of entries will automatically be only as many as there are non-duplicates in the input. The array length property will be whatever the largest integer is in the set but it will not be the number of entries in the array as most of the keys lower than that one will be missing from the array. The Object.keys() method that is built into modern JavaScript converts the sparse array of keys that we have built into a dense array where the values correspond to the keys in our original array.