CODEWITHSUNDEEP
javalong-integerhashset
Sreevathsa Gowru
Sreevathsa Gowru

Reputation: 65

Java HashSet (Long vs Integer)

I was solving this problem, (41 from Project Euler), where I noticed that contains method of HashSet is working differently for Long as compared to Integer (I might be wrong here, please correct me if I am).

The question is -

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

My code for checking whether the number is Pandigital or not is - 

private static boolean isPan(Long n) {
        HashSet<Long> list = new HashSet<Long>();
        int count = 0;
        while(n != 0){
            list.add(n%10);
            count++;
            n /= 10;
        }
        for(int i = 9; i>count; i--){
            if(list.contains(i)) return false;
        }
        for(int i = 1; i<= count; i++){
            if(!list.contains(i)) return false;
        }
        return true;
    }

This code gave me an infinite loop. So, I changed my code like this - 

private static boolean isPan(Long n) {
        HashSet<Integer> list = new HashSet<Integer>();
        int count = 0;
        while(n != 0){
            list.add((int) (n%10));
            count++;
            n /= 10;
        }
        for(int i = 9; i>count; i--){
            if(list.contains(i)) return false;
        }
        for(int i = 1; i<= count; i++){
            if(!list.contains(i)) return false;
        }
        return true;
    }

I just changed, HashSet<Long> to HashSet<Integer> and list.add(n%10) to list.add((int) n%10).

This gave me the correct answer, 7652413. So, can anyone explain why the contains method works differently for Long when compared to Integer?

Upvotes: 0

Views: 2870

Answers (2)

dabaicai
dabaicai

Reputation: 999

If you want your code run correctly,see your code whose list is HashSet<Long>:

for(int i = 1; i<= count; i++){
    if(!list.contains(i)) return false;
}

you can change the type of variable i to long,or change if(!list.contains(i)) return false; to the if(!list.contains(Long.valueOf(i))) return false;

Because of the contains will check element in existence by the element's method equals.In above code,the variable i is auto-boxed to Integer instance,because the variable i is primitive int. And see the Integer equals:

public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

but your list element's type is Long,so the line if(!list.contains(i)) return false; will return false always.

Upvotes: 0

Andreas
Andreas

Reputation: 159135

contains(Object o) method doesn't work different for Long vs Integer. It works exactly the same, i.e.

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

Notice however that method accepts Object as parameter type, not E. That means you can call it with any type of object. Of course, any object type other than E would cause it to return false, since equals() would fail for objects of different types (with some exceptions).

So, when you call contains(x), and x is a primitive, it will be auto-boxed, based on the type of x, not on the type of E. So if x is an int and E is Long, it'll always return false.

It is not contains() that suddenly works different, when you change Long to Integer. It is your code that works different, by correctly matching the type of value passed to contains() to the type of elements in the collection.

UPDATE

Your code is not very efficient:

  • It takes a Long as a parameter, but max n is by nature 9, and and int can store 9-digit numbers without overflow, so use of Long, and use of boxing, is unnecessary.

  • It allocates a new HashSet for every value being checked, and autoboxes every digit found, plus 9 times for the contains() calls.

Instead, this can be done using bit-manipulation, since as 32-bit int value can easily store 10 boolean values (flags) indicating whether a digit was present.

The code below will establish two bit-masks, found and expected, which will indicate whether a digit is found, and whether a digit was supposed to be found. Since solution should only use digits 1-n, we'll claim digit 0 is present and expected (makes logic simpler, not having to do special checks for 0).

If a digit is presented twice (or digit 0 is presented once), another expected digit will be missing, and found will not equal expected.

private static boolean isPandigital(int number) {
    int found = 1, expected = 1;
    for (int n = number; n != 0; n /= 10, expected = (expected << 1) | 1)
        found |= 1 << (n % 10);
    return (found == expected);
}

Upvotes: 4

Related Questions