2

Consider 9 variables that can have values from to 1 to 9 each. What is a good and fast way to check if each variables has a distinct value. The first thought came to my mind was to sum them up to see if it is equal to n(n+1)/2 but this is nowhere foolproof. Any ideas?

Edit : Thanks a lot guys. Totally forgot about Set. What a noob I am.

karmanaut
  • 628
  • 1
  • 6
  • 17
  • 2
    look up `java.util.Set` – yshavit Apr 05 '13 at 14:29
  • "good and fast" depends on if you are looking for a solution to this particular problem (numbers limited from 0-9) or a general solution that scales well as the number of values increases. – mbeckish Apr 05 '13 at 14:32
  • 2
    Is it really 9 variables and 10 possible values (0-9), or did you misstate the problem? – mbeckish Apr 05 '13 at 14:33

4 Answers4

6

Add them all to a Set, and check that the size of the Set is 9.

For example, to check if an array of 9 int are all different:

int[] array = new int[9];
// fill array
Set<Integer> set = new HashSet<Integer>();
for (int i : array)
    set.add(i);
boolean allDistinct = set.size() == 9;

The set does all the work, because sets only allow distinct values to be added. If any values are the same, the size will be less than 9.

This technique works for any class of value types, any range and any quantity of values.

Bohemian
  • 412,405
  • 93
  • 575
  • 722
  • 1
    @maba the OP said: `Consider 9 variables that can have values from to 0 to 9 each`. – Eng.Fouad Apr 05 '13 at 14:33
  • Totally missed the use of Set. Thank you. I feel silly now asking this question :) Answer accepted. – karmanaut Apr 05 '13 at 14:37
  • 1
    Also note that you can put a stop condition checking the size in the for-loop to stop early. For 9 elements it doesn't matter that much, but 9 elements may just have been an example. – Bernhard Barker Apr 05 '13 at 16:42
6

Start with a bitmask with bits 0 through 9 set, then clear the bits corresponding to values of each variable. If the resultant bitmask is a power of two, all values were distinct+; otherwise, there were duplicates.

int a, b, c, d, e, f, g, h, i;
int mask = 0x3FF; // bits zero through 9 are set
mask &= ~(1<<a);
mask &= ~(1<<b);
...
mask &= ~(1<<i);
if ((mask & -mask) == mask) {
    // all bits were distinct
}

See this answer for an explanation of the bit trick used in the last condition.

+ You have ten possible values and nine variables; in order for the nine values to be distinct, they must clear out nine out of ten bits from the bitmask with all ten bits initially set. Removing nine out of ten bits leaves you with only one bit set to 1, meaning that the result is a power of two.
Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • +1 Good old semi-obscure bit hackery; this makes people feel like wizards. Plus it is the most efficient way to do it, since hashing and a histogram will require some data structures which take time to build. – G. Bach Apr 05 '13 at 17:59
4

Use XOR to find the duplicate number is a trick. 

int[] arr = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 5, 9 };
int answer = 0;
for (int i = 0; i < arr.length; i++) {
    answer = answer ^ (arr[i] + 1) ^ i;
}
System.out.println(answer - 1);

Output:

5
Achintya Jha
  • 12,735
  • 2
  • 27
  • 39
0

This algorithm is working with any count of number, but every number must be in interval <0, 31> or you can change mask and bit type to long for interval <0, 63>.

int[] numbers = {0, 1, 2, 3, 3, 5, 6, 7};

int mask = 0;
for (int number : numbers) {
    int bit = 1 << number;

    if ((mask & bit) > 0) {
        System.out.println("Found duplicity " + number);
        return;
    }

    mask |= bit;
}

System.out.println("No duplicity");
Thomas.
  • 91
  • 2
  • 6