dailyalgorithm

Find The Parity Outlier

algorithm

Instructions

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 this “outlier” N.

Example:

1
2
3
4
5
[2, 4, 0, 100, 4, 11, 2602, 36]
Should return: 11 (the only odd number)

[160, 3, 1719, 19, 11, 13, -21]
Should return: 160 (the only even number)

My solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class FindOutlier {
    public static int find(int[] integers) {
        int positiveIfEven = -1;

        if (isEven(integers[0]))
            positiveIfEven++;

        if (isEven(integers[1]))
            positiveIfEven++;

        if (isEven(integers[2]))
            positiveIfEven++;

        if (positiveIfEven > 0)
            return findOdd(integers);

        return findEven(integers);
    }

    public static boolean isEven(int num) {
        return (num & 1) == 0;
    }

    public static int findEven(int[] integers) {
        int arrLength = integers.length;
        for (int i = 0; i < arrLength; i++) {

            if (isEven(integers[i]))
                return integers[i];

        }

        return 0;
    }

    public static int findOdd(int[] integers) {
        int arrLength = integers.length;
        for (int i = 0; i < arrLength; i++) {

            if (!isEven(integers[i]))
                return integers[i];

        }

        return 0;
    }
}

Better solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.Arrays;

public class FindOutlier {
    public static int find(int[] integers) {
        // 3개의 element의 2 modulus 연산값의 합
        // 홀 홀 홀 = 3
        // 홀 홀 짝 = 2
        // 홀 짝 짝 = 1
        // 짝 짝 짝 = 0
        int sum = Arrays.stream(integers)
                .limit(3)
                .map(num -> Math.abs(num) % 2)
                .sum();

        // 짝이면 홀수를 찾아야 한다 mod = 1
        // 홀이면 짝수를 찾아야 한다 mod = 0
        int mod = (sum == 0 || sum == 1) ? 1 : 0;

        return Arrays.stream(integers)
                .filter(num -> Math.abs(num) % 2 == mod)
                .findFirst()
                .getAsInt();
    }
}

feeling

처음 3개의 element를 통해 array의 패턴이 odd인지 even인지 파악하는 접근은 나쁘지 않았던 것 같다.

다만 그 이후 패턴이 다른 element 찾는 로직이 복잡했던 것 같다.

함수형 프로그래밍을 공부하자!

Share