0

I am unsure as to why my code does not give the correct outputs for the test data which has been provided to me.

Write a procedure 'allDistinct' that takes an array of objects and returns true iff they are all distinct (no two identical).

Your procedure must work for all classes, You may type it using a variable type T

<T> boolean allDistinct(T[] a)
{
    boolean r = true;
    
    for (int i = 0; i < a.length; i++)
    {
        for (int j = 0; j < a.length; j++)
        {
            if (a[i] == a[j])
            {
                r = false;
            }
        }
    }
    
    return r;
}

test results

I have tried using .equals() instead of == but this resulted in no change and I am not sure why it is still incorrect.

Mureinik
  • 297,002
  • 52
  • 306
  • 350
Fahim
  • 11

3 Answers3

1

This is very simple task.

First of all, you should compare two objects with type T using equals().

Your task is to put all data into a HashSet collection. And if the final size of the collection is less thant the length of the array, it means, that the array contains not distinct values.

public static <T> boolean isAllDistinct(T[] arr) {
    Set<T> unique = new HashSet<>();

    for (T item : arr)
        if (!unique.add(item))
            return false;

    return true;
}

or using Stream

public static <T> boolean isAllDistinct(T[] arr) {
    return Arrays.stream(arr).collect(Collectors.toSet()).size() == arr.length;
}
Oleg Cherednik
  • 17,377
  • 4
  • 21
  • 35
1

First, you were right, you absolutely need to use equals and not == (see, e.g., What is the difference between == and equals() in Java?).

Second, as Umeshwaran's answer's states, by "naively" looping over i and j, you have multiple cases where i and j are the same, and thus you'd be comparing an object to itself and wrongly returning false.

Third, while this has no effect on the correctness of the solution, from a performance perspective you should use the early return idom. Once you found a duplicate value there's no chance of it getting "unduplicated", so it's pointless to continue iterating over the rest of the array:

<T> boolean allDistinct(T[] a) {
    for (int i = 0; i < a.length; i++)  {
        for (int j = i + 1; j < a.length; j++) {    // changed j=0 to j=i+1
            if (a[i] == a[j]) {
                return false; // Early return
            }
        }
    }
    
    return true;
}

Having said all of that, it may be easier to let Java's Sets do the heavy lifting for you, although this is tradeoff between runtime complexity and memory complexity:

<T> boolean allDistinct(T[] a) {
    Set<T> tempSet = new HashSet<>(Arrays.asList(a));
    return tempSet.size() == a.length;
}
Mureinik
  • 297,002
  • 52
  • 306
  • 350
0

Your code is correct , but you have made a minor mistake which is making it false .

<T> boolean allDistinct(T[] a)
{
    boolean r = true;
    
    for (int i = 0; i < a.length; i++)
    {
        for (int j = i+1; j < a.length; j++)     // changed j=0 to j=i+1
        {
            if (a[i] == a[j])
            {
                r = false;
            }
        }
    }
    
    return r;
}

I have changed j=0 to j=i+1 , because when looping again , you are checking if both first elements are equal and it is failing

Umeshwaran
  • 627
  • 6
  • 12