Return true if the elements of an array do not contain one or the other

Question

I am gradually completing the CodingBat exercises for Java. Here is the one I just did:

Given an array of ints, return true if it contains no 1's or it contains no 4's.

Here is my code:

public boolean no14(int[] nums) {

    int oneCount = 0;
    int fourCount = 0;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
            oneCount++;
        }
        if (nums[i] == 4) {
            fourCount++;
        }
    }

    if (oneCount > 0 && fourCount > 0) {
        return false;
    }
    return true;
}

Now, I am pretty unfamiliar with arrays, so I would just like to know if there is a simpler/shorter way of finding such information without setting a count for each number? Perhaps using a regular expression?

Answer 1

In JDK there's nothing, but with Guava you could do

List<Integer> list com.google.common.primitives.Ints.asList(nums);
return !(list.contains(1) && list.contains(4));

Obviously, converting int[] to something like ArrayList<Integer> would be a performance disaster. Fortunately, there's nothing like this, instead there's a class implementing the List interface by accessing the primitive array. Bulk-methods like contains are optimized and lead to a simple loop with no boxing inside.

---

But seriously, feel free to stick with your loop, as there's not always such a trick available. What you could improve:

• You need no xxxCount, a simple boolean containsXxx would do. But this is no problem, having the count may be useful sometimes.
• You could use an early return. Whenever you find a 1, you can check if you have already a 4 and return false if so.

---

The only part I dislike is

if (oneCount > 0 && fourCount > 0) {
    return false;
}
return true;

You surely mean

return oneCount == 0 || fourCount == 0;

---

If performance was very important (which it rarely is), I'd try this

int i = 0;
int missing;
for (; ; i++) {
    if (i == nums.length) {
        return true;
    } else if (num[i] == 1) {
        missing = 4;
        break;
    } else if (num[i] == 4) {
        missing = 1;
        break;
    }
}
for (; i < nums.length; i++) {
    if (nums[i] == missing) {
        return false;
    }
}
return true;

But as you can see, it's terribly long and not very readable. When embedded in a real code it may also be slower (due to inlining limit or whatever).

Answer 2

Generally, your naming is good. I never like nums as a name, but sometimes, like in this case, it's hard to see anything more descriptive. Perhaps just numbers. no14 is also not a great name, though since this is testing something so specific, there probably aren't many candidates. emptyOfOnesOrFours or similar might be better, cumbersome as it is.

---

As for code, the algorithm is a good and clear start, but let's see if we can do any better with the code through refactoring.

First, we can see that there's actually there's actually a lot of the same code being done separately for 1 and 4. Imagine if you added, say, six more numbers to that list, and you'd see a lot of repetition emerging. So the first thing to do would be to extract that into a method:

private boolean contains(int[] numbers, int target) {
    int targetCount = 0;

    for(int i=0; i<numbers.length; i++) {
        if(numbers[i] == target) {
            targetCount++
        }
    }
    if(targetCount > 0) {
        return false;
    }
    return true;
}

Now that we've done this, we can see an obvious simplification:

private boolean contains(int[] numbers, int target) {

    for(int i=0; i<numbers.length; i++) {
        if(numbers[i] == target) {
            return true;
        }
    }
    return false;
}

Now our original method can read much clearer:

public boolean emptyOfOnesOrFours(int[] numbers) {
    return !contains(numbers,1) || !contains(numbers,4);
}

(That's just about pushing the complexity of what I'd want in a single line, so depending on taste you could separate that out by first assigning the individual contains calls to booleans.)

Answer 3

At first, I was curious why the question was phrased as "not containing 1 or 4", the stream-based solution here seems to suggest why:

public static boolean hasNoOneAndFour(int... values) {
    return Arrays.stream(values).filter(i -> i == 1 || i == 4).distinct().count() != 2;
}

Picking out only the values 1 and 4 (filter(i -> i == 1 || i == 4)) is understandable, how can one check that we have both 1 and 4 in the end? I went with a distinct() operation and then counting that we do not have both values...

Answer 4

If you don't want to include a library for such simple problem, do it this way:

static boolean no14(int[] ints){
    // make copy if you don't wont to modify the input
    int[] copy = ints.clone();

    Arrays.sort(copy); // O(n log n)

    return Arrays.binarySearch(ints, 1) >= 0 && Arrays.binarySearch(ints, 4) >= 0;
}

If your input is small, do not worry about sorting.

Answer 5

You don't need to count ones and fours, since you can return false at the first sight of either one.

public boolean no14(int[] nums) {

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1 || nums[i] == 4) {
            return false;
        }
    }
    return true;
}