CODEWITHSUNDEEP
java
paul
paul

Reputation: 21

Figuring out if all but one array elements are identical

Does anyone know how I would work out if all elements in an array but one have the same value?

I have been trying to work it out for ages but cannot solve it. For example testing an array that has 5 elements to see if it has 4 identical values.

Thanks

Upvotes: 2

Views: 1303

Answers (7)

Ashok
Ashok

Reputation: 461

  1. Iterate array, by comparing 1st element and x+1 elements where x is 2,3,4,...array.length()
  2. If comparison fails then increment a counter

if ((counter==0) || ((counter> 1) && (counter != array.length-1))) then condition is not met

counter=0 means, all are same elements

counter=array.length-1 means sorted order eg: 4,5,5,5,5,5,5

Complexity ->time: O(n), no extra space other than counter

Upvotes: 1

pmnt
pmnt

Reputation: 379

You could also add all array elements into a LinkedHashSet (no duplicates, insertion order is preserved) and look at the set's .size()

Upvotes: 0

aioobe
aioobe

Reputation: 420951

Here's another approach:

public static <Item> boolean allButOneSame(List<Item> items) {

    // Make sure we have 2 different elements (or 1 element in total)
    if (new HashSet<Item>(items).size() != 2)
        return items.size() == 1;

    // Create a temporary copy
    List<Item> tmp = new ArrayList<Item>(items);

    // Remove all elements equal to the first one.
    tmp.removeAll(Collections.singleton(items.get(0)));

    // Check the number of remaining elements.
    return tmp.size() == 1 || tmp.size() == items.size() - 1;
}

It takes a List as input. Use Arrays.asList if start with an array.

Upvotes: 0

aioobe
aioobe

Reputation: 420951

I came up with this trick :-)

public static boolean allButOneSame(int[] arr) {
    if (arr.length <= 1)
        return arr.length == 1;

    Arrays.sort(arr);

    return  arr[0] != arr[arr.length-1] &&
           (arr[0] == arr[arr.length-2] ||
            arr[1] == arr[arr.length-1]);
}

(Relies on comparable values such as integers though!)

Upvotes: 1

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298878

Use a map.

Map<X, Integer> map = new HashMap<X, Integer>(); // where X is the array type
Integer ct;
for(X item : array){
    ct = map.get(item);
    if(ct == 0) ct = Integer.valueOf(1);
    else ct = Integer.valueOf(ct.intValue()+1);
    map.put(item, ct);
}
// now test if map.values() consists of Integer.valueOf(1) and (optionally)
// another positive integer (thx aioobe)

Upvotes: 4

leifg
leifg

Reputation: 8988

The approach I would choose is:

iterate over all elements and put them in a Map (HashMap in Java).

the key is the element, and the value is the counter of the appearance.

example: your array: A A A A B

map:

A -> 4 B -> 1

After you have constructed that map it's easy to find out if your array matches that criteria.

  1. The map must have exactly 2 elements (map.size()).
  2. Exactly one of the elements has the counter 1.

If you assume that adding to a map happens in constant time you'll have an overall complexity of 2n (iterate over array and iterate over map).

Upvotes: 2

SJuan76
SJuan76

Reputation: 24885

Step by Step:

  1. Get the first element.

  2. Loop all the array elements and count the number of times they don't match that first element.

    • If all of the elements match, you have your answer (all are equal).
    • If only one of the elements do not match, you have your answer (one is different).
    • If some of the elements do not match, you have your answer (more than one is different).

  3. In none of the elements match, get the second element and repeat the test.

    • If only one of the elements do not match, again only one is different (the first one).
    • Else, the number of different elements is bigger than one.

Upvotes: 2

Related Questions