# Find The Parity Outlier

I am trying to solve this coding exercise:

You are given an array (which will have a length of at least 3, but could be very large) containing integers. The array is either entirely comprised of odd integers or entirely comprised of even integers except for a single integer N. Write a method that takes the array as an argument and returns N.

For example:

[2, 4, 0, 100, 4, 11, 2602, 36]

Should return: 11

[160, 3, 1719, 19, 11, 13, -21]

Should return: 160

Here is my code:

import java.util.ArrayList;
public class FindOutLier {
public static int search(ArrayList<Integer> lists, int num) {
int count = 0;
int index;
Integer a[] = new Integer[lists.size()];
a = lists.toArray(a);
for (index = 0; index < a.length; index++) {
if (num == a[index]) {
count++;
}
}
return count;
}

public static boolean checkEvenOrOdd(int[] integers) {
int t = 0;
double result = 0.0;
ArrayList<Integer> l = new ArrayList<Integer>(integers.length);
while (t < integers.length) {
result = integers[t] % 2;
if (result == 0.0) {
t++;
} else {
t++;
}
}
int counter = search(l, 1);
if (counter == 1)
return true;
else
return false;
}

public static int find(int[] integers) {
int t = 0;
double newresult = 0.0;
boolean result = checkEvenOrOdd(integers);
if (result == false) //
{
while (t < integers.length) {
newresult = integers[t] % 2;
if (newresult != 0.0) {
break;
} else {
t++;
}
}
} else {
while (t < integers.length) {
newresult = integers[t] % 2;
if (newresult == 0.0) {
break;
} else {
t++;
}
}
}
return integers[t--];
}
}


It passed Junit Test in Eclipse. Please review it/ suggest any improvements. Thanks.

• First thing would be to make it easier readable. Indent as appropriate, add space between functions, remove unused comment marks. And place a few comments outlining your general approach. – bdecaf Oct 2 '17 at 7:12
• I have added a link to what (I think) is the source of the problem. Please check if that is correct. – Martin R Oct 2 '17 at 8:19

Your approach is far too complicated.

• In checkEvenOrOdd() you create a ArrayList<Integer> containing zeros or ones.
• In search() you create an Integer a[] from that list.
• Then you iterate over the array and count the number of zeros or ones.

You can iterate over int[] integers directly to find the number of odd (or even) entries:

    int oddCount = 0;
for (int n : integers) {
if (n % 2 != 0) {
oddCount += 1;
}
}


Note how a "enhanced for statement" can be used to iterate over the array elements, instead of a for-loop or a while-statement for the array indices, as in your code.

There is also no need to use a double result or floating point literals when doing an integer remainder calculation.

    if (counter == 1)
return true;
else
return false;


can be simplified to

    return (counter == 1)


But in this case the entire logic can be put into a single function, e.g. like this:

public static int find(int[] integers) {

int oddCount = 0;
for (int n : integers) {
if (n % 2 != 0) {
oddCount += 1;
}
}

if (oddCount == 1) {
for (int n : integers) {
if (n % 2 != 0) {
return n;
}
}
} else {
for (int n : integers) {
if (n % 2 == 0) {
return n;
}
}
}
return 0;
}


Then one could try to avoid the code repetition for the even/odd case.

But actually I would suggest a completely different, more efficient approach:

• Check the first two array elements if they are even or odd.
• If they are both even, the outlier can be found by search for the first odd element, starting at index 2.
• If they are both odd, the outlier must be even, and can be found similarly.
• If the first two array elements have different parity, one of them is the outlier. Which one, can be determined by checking the third array element.
• when I executed this code at ECLIPSE ide it was properly executed, but the same code when executed through coding site server resulted in - "SYMBOL NOT FOUND " in lines 27 - 29 and 57-71. Is there a problem in code itself or what , I could not understand. The server uses Junit to test the code. – mJAY Oct 2 '17 at 9:57
• @mJAY: I have added the code which runs without problems in my test. – Martin R Oct 2 '17 at 10:11
• The last proposed approach is simple, efficient and elegant and should be the 'real' solution :) – RobAu Oct 3 '17 at 12:34

I found much simpler and efficient option instead of traversing through entire array twice. all we need is to compare three successive elements look for outlier between them if not continue the loop until you find one and reach end of the of loop. i unit tested this and covers all the cases.

public int findOutLierIndex(int[] input) {
int result = -1;

if (input != null && input.length > 2) {

for (int i = 2; i < input.length; i++) {
if (isEven(input[i]))
if ( isOdd(input[i - 1]) && isOdd(input[i - 2]))
return i;
if ( isEven(input[i - 1]) && isOdd(input[i - 2] ))
return i - 2;
else if ( isOdd(input[i - 1]) && isEven(input[i - 2]))
return i - 1;
if (isOdd(input[i]))
if (isEven(input[i - 1]) && isEven(input[i - 2]))
return i;
if (isOdd(input[i - 1]) && isEven(input[i - 2]))
return i - 2;
else if (isEven(input[i - 1]) && isOdd(input[i - 2]))
return i - 1;
}
}

return result;
}

public boolean isEven(int number){
return (number % 2 == 0);
}
public boolean isOdd(int number){
return (number % 2 == 1);
}

• This code is hard to read (because of all the repetitions of input[i - x]) and doesn't handle negative numbers correctly. Don't write x % 2 == 1, but instead x % 2 != 0. – Roland Illig Mar 16 '18 at 17:10
• Agree, Refactored for readability using isEven and isOdd. – Kishore Mar 31 '18 at 21:52