CODEWITHSUNDEEP
javaarraysduplicates
Suleman Qamar
Suleman Qamar

Reputation: 63

Array Duplicate Efficiency Riddle

Recently in AP Computer Science A, our class recently learned about arrays. Our teacher posed to us a riddle. Say you have 20 numbers, 10 through 100 inclusive, right? (these numbers are gathered from another file using Scanners)

As each number is read, we must print the number if and only if it is not a duplicate of a number already read. Now, here's the catch. We must use the smallest array possible to solve the problem.

That's the real problem I'm having. All of my solutions require a pretty big array that has 20 slots in it.

I am required to use an array. What would be the smallest array that we could use to solve the problem efficiently?

If anyone could explain the method with pseudocode (or in words) that would be awesome.

Upvotes: 1

Views: 129

Answers (6)

Naberhausj
Naberhausj

Reputation: 303

My last answer misunderstood what you were needing, but I turned this thing up that does it an int array of 5 elements using bit shifting. Since we know the max number is 100 we can store (Quite messily) four numbers into each index.

    Random rand = new Random();

    int[] numbers = new int[5];
    int curNum;

    for (int i = 0; i < 20; i++) {

        curNum = rand.nextInt(100);

        System.out.println(curNum);

        boolean print = true;
        for (int x = 0; x < i; x++) {

            byte numberToCheck = ((byte) (numbers[(x - (x % 4)) / 4] >>> ((x%4) * 8)));

            if (numberToCheck == curNum) {

                print = false;

            }

        }

        if (print) {

            System.out.println("No Match: " + curNum);

        }

        int index = ((i - (i % 4)) / 4);
        numbers[index] = numbers[index] | (curNum << (((i % 4)) * 8));

    }

I use rand to get my ints but you could easily change this to a scanner.

Upvotes: 0

user7583029
user7583029

Reputation:

Since an array cannot change size at run time You need a companion variable to count the numbers that are not duplicates and fill the array partially with only those numbers.

Here is a simple code that use companion variable currentsize and fill the array partially.

Alternative you can use arrayList which change size during run time

final int LENGTH = 20;
double[] numbers = new double[LENGTH];

int currentSize = 0;
Scanner in = new Scanner(System.in);
while (in.hasNextDouble()){
 if (currentSize < numbers.length){
 numbers[currentSize] = in.nextDouble();
 currentSize++;
 }
}

Edit

Now the currentSize contains those actual numbers that are not duplicates and you did not fill all 20 elements in case you had some duplicates. Of course you need some code to determine whither a numbers is duplicate or not.

Upvotes: 0

Calculator
Calculator

Reputation: 2789

If your numbers are integers: You have a range from 10 to 100. So you need 91 Bits to store which values have already been read. A Java Long has 64 Bits. So you will need an array of two Longs. Let every Bit (except for the superfluous ones) stand for a number from 10 to 100. Initialize both longs with 0. When a number is read, check if the corresponding bit mapped to the read value is set to 1. If yes, the read number is a duplicate, if no set the bit to 1.

This is the idea behind the BitSet class.

Upvotes: 2

Jorn Vernee
Jorn Vernee

Reputation: 33885

You technically don't need an array, since the input size is fixed, you can just declare 20 variables. But let's say it wasn't fixed.

As other answer says, worst case is indeed 19 slots in the array. But, assuming we are talking about integers here, there is a better case scenario where some numbers form a contiguous interval. In that case, you only have to remember the highest and lowest number, since anything in between is also a duplicate. You can use an array of intervals.

With the range of 10 to 100, the numbers can be spaced apart and you still need an array of 19 intervals, in the worst case. But let's say, that the best case occurs, and all numbers form a contiguous interval, then you only need 1 array slot.

The problem you'd still have to solve is to create an abstraction over an array, that expands itself by 1 when an element is added, so it will use the minimal size necessary. (Similar to ArrayList, but it doubles in size when capacity is reached).

Upvotes: 1

Evgeny Semionov
Evgeny Semionov

Reputation: 323

Agree with Socowi. If number of numbers is known and it is equal to N , it is always possible to use N-1 array to store duplicates. Once the last element from the input is received and it is already known that this is the last element, it is not really needed to store this last value in the duplicates array.

Another idea. If your numbers are small and really located in [10:100] diapason, you can use 1 Long number for storing at least 2 small Integers and extract them from Long number using binary AND to extract small integers values back. In this case it is possible to use N/2 array. But it will make searching in this array more complicated and does not save much memory, only number of items in the array will be decreased.

Upvotes: 1

Socowi
Socowi

Reputation: 27255

In the worst case we have to use an array of length 19. Why 19? Each unique number has to be remembered in order to sort out duplicates from the following numbers. Since you know that there are 20 numbers incoming, but not more, you don't have to store the last number. Either the 20th number already appeared (then don't do anything), or the 20th number is unique (then print it and exit – no need to save it).

By the way: I wouldn't call an array of length 20 big :)

Upvotes: 3

Related Questions