2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ regex for this? now you have 3 problems, the original one, turning it into a regex and making a regex engine for an int array. \$\endgroup\$ – ratchet freak Apr 14 '15 at 10:30
3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Really? You're going to convert the int[] array to a List<Integer>? \$\endgroup\$ – rolfl Apr 14 '15 at 17:06
  • \$\begingroup\$ @rolfl Why not? It's not an ArrayList. See the doc. It's less efficient than looping manually, but only by a small constant; the contains method is full speed. \$\endgroup\$ – maaartinus Apr 14 '15 at 17:11
  • \$\begingroup\$ Hmm, it is still not good, not as bad as I thought, but the instance overhead, and autoboxing additions put neat code in front of an ugly backend. I see that you do recommend an early-exit on finding both, hat suggestion is the most valuable part as far as I can tell. Unfortunately my down-vote is locked in until your post is edited... \$\endgroup\$ – rolfl Apr 14 '15 at 17:23
  • \$\begingroup\$ @rolfl Edited. There's a single unboxing inside the call to contains, that's all. \$\endgroup\$ – maaartinus Apr 14 '15 at 17:48
3
\$\begingroup\$

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.)

\$\endgroup\$
  • 1
    \$\begingroup\$ It may actually have better performance, as each of the loops stop once they hit the expected value, and the cost of doing two small loops versus one larger loop isn't too big. \$\endgroup\$ – Nathan Merrill Apr 14 '15 at 14:23
  • \$\begingroup\$ @MrTi Good point! I removed that last paragraph, since I think going into analysis of the more/less performant scenarios and their relative probabilities would be overkill. \$\endgroup\$ – Ben Aaronson Apr 14 '15 at 14:44
1
\$\begingroup\$

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...

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Assuming I understand the problem, you code is wrong. \$\endgroup\$ – maaartinus Apr 14 '15 at 12:02
  • \$\begingroup\$ @CamelFace Please read the question. No 1s OR no 4s. \$\endgroup\$ – alanbuchanan Apr 14 '15 at 12:06
  • \$\begingroup\$ Welcome to CodeReview, CamelFace. Please try to read the question carefully! \$\endgroup\$ – Legato Apr 14 '15 at 13:08
  • \$\begingroup\$ I agree with others, that you misread the question slightly, but you have also seen an optimization that nobody else has, just implemented it wrong. +1 for the fail-faster suggestion. \$\endgroup\$ – rolfl Apr 14 '15 at 16:57
  • \$\begingroup\$ I think the question should be phrased as "no 1s and 4s"... \$\endgroup\$ – h.j.k. Apr 15 '15 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.