You can download my solution here:
http://www.site.uottawa.ca/~mraap046/code/ReadArray.java
The other solution above needs an array of size 20. My solution only needs an array of size 2, so my array is much smaller and the smallest possible!
The idea here is that in a long number (which is just a fancy way of saying a big integer), internally the computer represents the number using binary (as it does everything in the computer). In this case, a long number consists of 64 bits, or 64 positions of values either 0 or 1.
We can actually use a long number, then, as an array of boolean values of length 64, where position i is 0 if value i is false and 1 if value i is true. So here, we can represent a set of numbers whose values are between 0 and 63 using a long. To understand this better, I'll do a simpler example. Say that instead of 64 values, we only have 8 values. Then we can represent any subset of elements from from {0,1,2,3,4,5,6,7}. For example, to represent the subset 0, 1, 2, we have the binary:
1 1 1 0 0 0 0 0
because positions 0, 1, and 2 are 1, so they are in the subset, and 3, 4, 5, 6, and 7 are 0, so they are not in the subset. For another example, the subset 0, 4, 7 is:
1 0 0 0 1 0 0 1
because positions 0, 4, and 7 are 1 and the other positions are all 0. Get it?
Anyways, we can think of the list of unique numbers as a subset of {10, 11, 12, ..., 99}, which contains 90 numbers. Each long can represent all the subets of a set of size 64, so two longs will let us represent all the subsets of a set of size 2*64 = 128. Since our set here has size 90, that's more than enough.
In computer architecture, instead of working left and moving right like we did above (e.g. having subset {1,3} of {0,1,2,3,4,5,6,7} as 01010000), we'll work from right to left (so {1,3} of {0,1,2,3,4,5,6,7} is just the mirror image, e.g. 00001010, so the right-most position represents element 0, the next element 1, etc).
So now, to represent a subset of {10, ..., 99} with two longs, which is what we want to do (and will let us get all the unique elements of our list), for a number i in {10, ..., 99} we need to figure out two things:
1. which of the two longs it is in, and
2. what is its position in that long.
This is actually really easy. First off, it's easier if we work with a list of numbers starting with 0, so we will actually just start by taking i-10, which means we will have a number in {0, ..., 89} instead. Now, the first long can represent a subset of a set of 64 values, so it will represent subsets of {0, ..., 63}, and the second will represent subsets of the rest, namely {64, ..., 89}.
If we take i / 64, then, this is integer division so it gives us the integer part of the division. So if i is between 0 and 63, it gives us 0, and if i is between 64 and 89, it gives us 1. So we'll use i / 64 to determine which long we use to represent i.
Then, the position in the long can be determined using i % 64, which gives the remainder when we divide by 64. So if i is between 0 and 63, it will simply return i, and if i is between 64 and 89, it gives us i-64.
Thus, if we have an array of long of size 2, say array:
long[] array = new long[2];
Then the position we will use to represent whether i is in the subset will be position i % 64 of array[i / 64]. We can determine if position i % 64 of array[i/64] is 0 or 1 through the operation:
array[i / 64] & (1 << (i%64))
What this does is it gets the value in position i%64 of array[i/64]. If the value is 0, then i is not in the subset, and if it is 1, then i is in the subset.
We can set the value in position i % 64 of array[i/64] to 1 using:
array[i / 64] = array[i / 64] | (1 << (i%64));
So those two operations are all you need to solve the problem.
Here is the output from the program:
Using an array of type long of size 2 (Long.SIZE = 64)
The original set of numbers are:
12 12 30 12 45 66 78 30 82 19 99 11 11 15 31 18 51 17 12 17
The different numbers from the set of integers are: 11 12 15 17 18 19 30 31 45 51 66 78 82 99
Not only does this use the smallest possible array (2, although your teacher is probably expecting size 20 so this is much better), but it is EXTREMELY efficient: adding an element can be done in 1 step regardless of whether or not it is already in the subset. Checking to see if an element is in the subset can also be done in constant time. Using the normal technique of having an array of size n=20 would take O(n^2) steps to add the elements, avoiding duplicates. Here, we need only O(n) steps: thus, much more efficient by an order of magnitude.
In the regular representation, outputting all the elements takes O(n) steps. Here, we need O(k) where k is the size of the set (here it's 99 - 10 + 1 = 90). So this is where the different lies.