Filter non-even elements from an array

Question

I have a method that returns an int[]. The array is made by filtering out only the even values of the array passed into the method.

It works, but it's really ugly and inefficient. How can I condense this and do it more efficiently?

import java.util.Arrays;
public class SequentialSearcher {
 public static void main(String[] args) {
 int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
 System.out.println(Arrays.toString(even(arr)));
 }
 private static int[] even(int[] array) {
 int[] newArr = new int[array.length];
 for (int i = 0; i < array.length; i++) {
 if (array[i] % 2 == 0) {
 newArr[i] = array[i];
 }
 }
 int count = 0;
 for (int num : newArr) {
 if ((num % 2 == 0) && (num != 0)) {
 count++;
 }
 }
 int[] finalArr = new int[count];
 int j = 0;
 for (int k : newArr) {
 if (k != 0) {
 finalArr[j] = k;
 j++;
 }
 }
 return finalArr;
 }
}

• QuestionablePresence: Generally if you're refusing any of the modern additions (ArrayLists, iterators, inline functions etc) your code will always be incredibly verbose and ugly. It's fine to go this way to learn the basics, but once you get productive, try to (almost) never use plain arrays ever. 90% of times they're the worse option
• TorbenPutkonen: @QuestionablePresence Fortunately this is not the case in this particular problem. See Nayuki's answer below. :)

Answer 1

ArrayList would be fine for dynamically sized "arrays."

You could also count the even numbers in advance.

int[] array = {3, 1, 4, 1, 5, 9, 2, 6, 5};
int evenCount = 0;
for (int i = 0; i < array.length; ++i) {
 if (array[i] % 2 == 0) {
 ++evenCount;
 }
}
int[] evenArray = new int[evenCount];
int iEven = 0;
for (int i = 0; i < array.length; ++i) { // ... && iEven < evenCount
 if (array[i] % 2 == 0) {
 evenArray[iEven] = array[i];
 ++iEven;
 }
}
System.out.println("e" + Arrays.toString(evenArray));

As a goodie: the usage of Stream classes: to accomplish bulk operations.

int[] a = IntStream.of(array).filter(n -> n % 2 == 0).toArray();
int[] a = IntStream.of(array) // Turns array into a Stream of ints.
 .filter(n -> n % 2 == 0) // n is declared, and set the next element.
 // Predicate whether even; filters.
 .toArray(); // Collect the Stream values into an int[].

Streams are a kind of "iteration" and can be used for arrays, collections, files and such. They offer a huge expressiveness. For instance:

int[] a = IntStream.of(array).filter(n -> n % 2 == 0).sorted().toArray();
[2, 4, 6]

• Joop Eggen: @JollyJoker The OP seems a coding beginner, and Streams - though certainly worth it -, is complex. Should know the basics: how code and data actually works. Also performance is better, say for embedded devices (like car automation). But all that said, I agree with you that IntStream is what I would use.
• Akshansh Jain: Interesting. I did try it out by adding 10 M integers in ArrayList and 10 M integers in LinkedList. ArrayList did outperform LinkedList, addition on ArrayList took around 2.5 seconds and addition in LinkedList took around 4 seconds.
• TorbenPutkonen: @JollyJoker When using streams, you need to understand that every "->" operator is a method call. When you're dealing with large data, it will create overhead that multiplies the run time. There is never a simple "one size fits all" answer.
• TorbenPutkonen: @AkshanshJain It's not surprising if you understand how computer hardware works. ArrayList can take advantage in L1 and L2 caches. When you access an array sequentially, it is almost guaranteed that the next value is in L1 cache or at least in L2. When you use a linked list, the target of the link can be anywhere in the memory. Plus with a LinkedList there's an extra object allocation for each element when the list Node is created. The next exercise is to use one of the pure array based solutions below and time them.
• swpalmer: Since you're talking about efficiency, it's faster if you avoid a branch: java for (int i = 0; i < array.length; ++i) { evenCount += 1 - (array[i] & 1); }

Answer 2

Rejecting 0 as an even value is unexpected (or a bug, more likely):
Use doc comments!

To establish the count of even elements, just add up all numbers modulo 2 and subtract from total count, special casing special values as need be.

The obvious way to get the result described is to use Streams as answered by Joop Eggen.

Answer 3

In your spirit of using only raw arrays and not the collections framework like ArrayList, this is how I would reimplement your even() function:

int[] temp = new int[array.length];
int n = 0; // Prefix length of temp
for (int val : array) {
 if (val % 2 == 0) {
 temp[n] = val;
 n++;
 }
}
return Arrays.copyOf(temp, n); // Truncate

Answer 4

This seems like an obvious place to use an ArrayList.

ArrayList<Integer> result = new ArrayList<>();
for (int k : array) {
 if (k % 2 == 0) {
 result.add(k);
 }
}

Of course, it can/will depend on how you need/want to use the result--an ArrayList<Integer> obviously isn't quite the same as an int [].

Answer 5

If the filter does not need to be stable, you can use the following in-place algorithm:

Repeatedly find the index i of the first non-even element and the index j of the last even element. While i < j, swap the elements and repeat.

Truncate the array to j + 1 elements.

Answer 6

1. You are using two temporary arrays i.e. newArr and finalArr for a simple filtering operation, which seems unnecessary.
2. You are running for loop 3 times, making it an inefficient solution.
3. I would rename the function even to filterEvenValues. It makes it clear on what the function does.

You can use a single for loop and copy the even values into one temporary array and return it (Other solutions mentioned this already, so I will skip this).

Java has Streams. You can take benefit of that and make your code very simple and efficient.

You can use Arrays.stream followed by .filter() to compact your code:

private static int[] filterEvenValues(int[] array) {
 return Arrays.stream(array).filter(x -> x % 2 == 0)
 .toArray();
}

Explanation of above code: Arrays.stream(array) converts the array into a stream of values. Now you can apply any operation on these values. .filter() is one such operation which allows you to filter out values from the original array based on a condition (in this case, if a value is even). And finally, .toArray() converts the filtered values (in stream) back to an array.

Answer 7

As a minimal change to your program, you should keep a separate index for the array with only evens. This array will have too many elements, but you can allocate a new array with the right number based on this index.

import java.util.Arrays;
public class SequentialSearcher {
 public static void main(String[] args) {
 int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5};
 System.out.println(Arrays.toString(even(arr)));
 }
 private static int[] even(int[] array) {
 int[] tempArr = new int[array.length];
 int j = 0;
 for (int i = 0; i < array.length; i++) {
 if (array[i] % 2 == 0) {
 tempArr[j++] = array[i];
 }
 }
 int[] evens = new int[j];
 for (int i = 0; i < j; i++) {
 evens[i] = tempArr[i];
 }
 return evens;
 }
}

• greybeard: (return java.util.Arrays.copyOf(tempArr, j); instead? Sure beats System.arraycopy()...)(Oh, answered by Nayuki.)
• Peilonrayz: Davislor's, now deleted, comment was more informative about the approach. Your explanation to a beginner is somewhat lacking.